Computers:

Open Source Lowers Cost, Increases Value

Closed source can not compete with open source, because the cost of programming is nearly the entire cost for a software company. For example, if the design of a manufactured item costs 1000 times the cost to manufacture 1 unit when a million units are produced, then the design cost is an insignificant 1/1000th of the total cost. The replication and distribution costs of software are approaching zero, thus the design (programming) cost is approaching the total cost. Thus, any company that is not sharing the programming cost with other companies, is resource constrained relative to those companies which are sharing their programming costs. Tangentially, this is why patents on software retard maximum social value obtained from programming investment.

For-profit software companies gain market leverage and market-fitness by diversifying their products and/or services from the shared code at the top level of integration.

With standardized open source license on code, corporations can spontaneously share the cost of programming investment, without the friction, delay, risk, uncertainty, and complexity of multiple, multifarious, bilateral, ad hoc sharing negotiations.

Increased code reuse (sharing) lowers the programming cost for corporations, enabling them to focus capital on their market-fitness integration expertise-- where they generate profits.

Project Granularity of Code Re-use Limits Sharing, Cost Savings, and Value

Open source has reduced the total programming cost to corporations and end users, but due to project-level granularity of code reuse (i.e. sharing), this reduction is not maximized, and costs have not decreased for smaller companies and individual programmers in those cases where they can not spontaneously build derivative code incorporating only parts of projects. Although there has been a boom in diversity and market-fitness of software products, it is not maximized, which is the manifestation of the lack of cost reduction in the aforementioned cases.

The scale of open source reuse is limited by general lack of fine-grained reuse of code inherent in the lack of referential transparency in existing software languages. Instead, we primarily have reuse of entire projects, e.g. multiple companies from the exchange economy sharing programming investment on Linux, Apache server, Firefox browser, etc..It is not easy to reuse sub-modules (i.e. parts) from these projects in other projects, due to the lack of forethought and referential transparency (i.e. too much "spaghetti code" littered with hidden inextricable, interdependencies) in existing software language and design. The granularity of code reuse dictates the scale of shared investment, because for example fewer companies would find an incentive to invest in an entire project than to invest in reuseable code modules within projects, where those modules could be used in a greater diversify of derivative software. Increase the granularity of code reuse by orders-of-magnitude via referential transparency in software languages, then the sharing of programming cost will also increase by orders-of-magnitude. With orders-of-magnitude lower programming cost, then smaller companies and individual programmers will be able to move to the top of the food chain of integration, and there will be orders-of-magnitude faster rate of progress and diversity of market-fitness in software.

Increased Granularity of Re-use Will Transition from Reputation to Exchange Economy

As granularity of reuse of programming code increases via new software languages that incorporate referential transparency paradigms, the economics of contribution will need to become more fungible. Currently the economics of open source is funded by large corporations which have clear strategic paybacks for the projects they choose to invest in. At the project level of granularity, strategic ramifications are reasonable to calculate. However, as granularity of reuse increases, the diversity of scenarios of reuse will increase exponentially or greater, so thus it will become impossible to calculate a payback for a specific contribution.

Although some open source proponents have postulated that the "gift culture"[1] drives contribution, as diversity of contribution increases into smaller parts (instead of project-level contribution), the value of reputation will plummet in areas that reward free contribution. First, it will become much less necessary to gain social status in order to get other people to agree to work with you, as contribution will become disconnected from project objectives and a leader's ability to make a project succeed. Instead, contributors will need another payback incentive. Second, since the economic inputs of large corporations will diminish in significance, the value of reputation in gaining income (a job) will diminish. Instead individual programmers and smaller companies will create their own jobs, by creating more derivative software, given the lower cost of reuse of smaller modules. So the incentive to reuse increases as cost of reuse is lowered via increased granularity of referential transparency, but what will motivate contribution if the value of reputation diminishes? The answer is the value of reciprocity. Those who want to reuse, will become willing to contribute, if others who want to reuse are willing to contribute. This is an exchange economy.

Although some argue that gifting contributions is driven by the incentive to have your contribution merged into the code of the derivative software you use[3], yet with a referentially transparent programming model and automated builds from a repository, customized builds may have no ongoing maintenance. Moreover, if a bug-fix or improvement can increase the value (as defined below) of the source contribution it is fixing even if the price of the source contribution is lowered by the price requested for the fix, then existing derivatives are not discouraged from adopting the fix. Thus, the owner of the source contribution could become the gate-keeper for merging fixes into derivative works, not the owner of the derivative work, which thus decentralizes the process as compared to the gift economic model currently employed for open source.

Studying history, there are no instances where the "gift culture" scaled to an optimal free market. Gift cultures exist only where inefficient social hierarchies are subsidized by abundance, e.g. open source currently funded via large corporate contributions driven by the abundant unmet end user demand for software. However, every year in China, 1 out of 6 million college graduates can't find a job, and many more are underpaid and underutilized, the world is currently at a debt-saturation crossroads, and it is not clear how there will be sufficient abundance of jobs to employ the billions in the developing world. Exchange economies are how the free market optimally anneals best-fit and diversity in times of lack of the subsidy of abundance. Reputation is measured in fungible units, called money or in our case, more specifically the value of current active contributions.

The challenge is how to make the exchange of reusable small module contribution value fungible and efficient. The value of a module of code is determined by its exchange price and the quantity of derivative code that employs it. The price should be increased or decreased to maximize this value. The price is paid periodically in bulk by those distributing for-profit derivative software, not micro-payments. Typically the price would apply to a per installation (not per user) license, where upgrades (fixes and improvements) might be free to existing installations because the code is continually re-used in new derivative works that pay the price. Thus the proposed exchange economic model has an advantage over the gift model, in that upgrade costs are amortized over derivative software proliferation, instead of the service contract model.[4]

Copyright Codifies the Economic Model

So if for-profit derivative use of a contribution has a price, then contributing stolen code could destroy value. This is copyright, and is analgous in the gift (reputation) economy to the use of copyright in existing open source standard licenses to force that derivative works give credit the source contribution. In each economic model, copyright codifies the restrictions that make that model. Closed source is a command economy, free open source is a gift (reputation) economy, and priced open source is an exchange economy. Note since gift (reputation) economy relies on social status and abundance subsidy, it does not economically maximize spontaneous individual efforts, i.e. similarities to socialism.

Code:

Economic Model  Copyright Restriction
---------------------------------------
  Command          no derivatives, no copies
  Gift            no delisting the source
  Exchange        no selling of stolen source

Human language writing is mostly a gift (reputation) economy, because the writer gains upsell benefits as his ideas and reputation grow, even via those who re-distribute the writings without paying royalties. Programming is different from writing in a crucial aspect-- the end users never read the code and 99.9% of the population are not programmers[2] (and even amongst programmers, most do not read the code of every software they use). In the current hacker gift (reputation) economy model, programmers can gain value by building reputation amongst a smaller circle of peers who know their work well, and given the funding for contribution is coming from large corporations that have strategic interests met by the free sharing model, then prevention of theft adds no value. However, if granularity of reuse incentivizes a move towards more of an exchange economy model, then theft is parasite on value, as there is less upsell benefits when reputation is morphed from small circles of social hierarchy to wider scale exchange value, and so copyright will morph to codify that theft is not allowed. Note that value in the exchange economy is based on quantity of derivative reuse, thus it creates more value to incentivize free reuse where those derivatives will be reused in paid derivatives. Thus the differential pricing in exchange economics, i.e. free use for non-profit purposes or upstart business volumes, and volume discounts for-profit use.

There is not likely to be complete shift from reputation to exchange economics, but rather a blending of the two.

[1] Eric Raymond, Homesteading the Noosphere, The Hacker Milieu as Gift Culture, http://www.catb.org/~esr/writings/homesteading/homesteading/ar01s06.html

[2] http://stackoverflow.com/questions/453880/how-many-developers-are-there-in-the-world

[3] Eric Raymond, The Magic Cauldron, The Inverse Commons, http://www.catb.org/~esr/writings/cathedral-bazaar/magic-cauldron/ar01s05.html

[4] Eric Raymond, The Magic Cauldron, The Manufacturing Delusion, http://www.catb.org/~esr/writings/cathedral-bazaar/magic-cauldron/ar01s03.html

SLK currently supports the C, C++, Java and C# languages on all platforms. Note that the SLK parsers primarily consist of tables of integers as arrays and a very small parse routine that only uses the simple, and universally supported features of the language. This is in contrast to parser generators that produce recursive descent code. They must force a certain programming model on the user because the parsing code is intermixed with the user action code. SLK places no limits or requirements on the coding style of the user.

Performance comment from Fischer & LeBlanc (1991), page 120:

Since the LL(1) driver uses a stack rather than recursive procedure calls to store symbols yet to be matched, the resulting parser can be expected to be smaller and faster than a corresponding recursive descent parser.

Code:

def len( s : String ) : Int = s.length

def len( s : String ) : Int { s.length }

def len( s : String ) : Int { return s.length }

val len : String => Int = s => s.length

val len = (s: String) => s.length

val len : String => Int = _.length

object len {
  def apply( s : String ) : Int = s.length
}

Code:

def f( arg1, arg2 ) = arg1 + arg2

def f( arg1 )( arg2 ) = arg1 + arg2

Code:

Value: 5      [1,2,3]    abstract  abstract      abstract
Type:  Int    List[Int]  List[T]    Pair[U, V]    Iterable[T, Sub[_]]
Kind:  *      *          * -> *    * -> * -> *    * -> (* -> *) -> *

Code:

class Iterable[T, Sub]
{
  filter : T -> Bool -> Sub
}

class ListInt inherits Iterable[Int, ListInt] {}

Code:

class Iterable[T]
{
  filter : T -> Bool -> Iterable[T]
}

class List[T] inherits Iterable[T]
{
  filter : T -> Bool -> List[T]  // an override
}

Code:

class Iterable[T, Sub[_]]
{
  filter : T -> Bool -> Sub[T]
}

class List[T] inherits Iterable[T, List] {}

Code:

\s -> s.length

Code:

len : Int -> Int = \s -> s.length

Code:

len (public,public) : Int -> Int = \s -> s.length

Code:

private len : Int -> Int = \s -> s.length  // as in Scala, private may be qualified with a package name, e.g. private[name]

Code:

len : Int -> Int

Code:

len = \s -> s.length

Code:

len : Int -> Int -> Int = \s, &pos = 0

Code:

len = \s, pos -> s.substring( pos ).length

Code:

val mult = (x: Int, y: Int): Int => x * y

Code:

mult : Int -> Int -> Int = \x, y -> x * y

Code:

mult (public, public) : Int -> Int -> Int = \x, y -> x * y

Code:

sources:
  { source }+
 
  source:
      class
      reference
      expression
      ifElse        // TODO: move this to 'primary' and change 'then' to use 'exprSansIfelse' instead of 'expression', and add 'else' to that line
     
  scope:
      '{' [ NL ] sources [ NL ] '}'
     
reference:
  [ refType ] ID typeInit    // without refType, defaults to 'cref' for pass-by-reference, and 'var' for pass-by-value, instances
  refType ID init            // init without type is only allowed if prepended with a refType, because otherwise ambiguous with with an assignment expression, e.g. no way to obscure a reference of same name in outer scope or assignment expression reference name typo silently accepted as construction of new reference
 
  refType:
      'const'        // the instance can not be modified, regardless if it is pass-by-reference or pass-by-value
      'ref'          // the reference can be modified to point to a different instance, applies only to pass-by-reference instances
      'const' 'ref'  // combines the above meanings, note the reference is not constant.
      'var'          // 'const' 'var' is not allowed because has same meaning as 'const'
      'cref'        // 'const' 'cref' is not allowed because has same meaning as 'const'

  typeInit:
      : nfType [ [ NL ] typeInit2 ]  // init is optional if cType has a default constructor
      tArgList [ NL ] ':' fType [ NL ] '=' [ NL ] function
      //init        when refType is not specified, this is ambiguous with an assignment expression. Disambiguate from assignment when ID is not already declared. Note this means a typo on ID will silently fail assignment and create a reference that is never accessed (so maybe we can detect on compilation and error). To hide an ID of same name in outer scope, then refType must be specified. If we did not allow assignment to declare new references, then mixin inheritance of an interface would require verbose 'cref' prepended to method implementations (due to the type being already specified in the interface).

  init:
      '=' [ NL ] rightExpr
     
      typeInit2:
        init
        nextType [ NL ] '=' [ NL ] function
       
      nfType:
        cType          // include standard classes for the builtin types, Int, Float, String, Bool
       
      fType:
        nfType [ NL ] nextType
        fType2
     
        fType2:
            '(' fType ')' [ NL ] nextType
            'void' [ NL ] '->' [ NL ] xtype  // 'void' not an instance reference type, thus can not be a class, only allowed as a single argument or return type
       
        xtype:
            nfType
            '(' fType ')'

        type:
            nfType [ [ NL ] nextType ]
            fType2

        nextType:
            '->' [ NL ] xtype [ [ NL ] nextType ]
            '->' [ NL ] 'void'            // 'void' not an instance reference type, thus can not be a class, only allowed as a single argument or return type

function:
  fDecl [ NL ] fBody

  fDecl:
      [ purity ] '\' [ fArgs ]
     
      fArgs:
        fArg [ [ NL ] ',' [ [ NL ] fArgs ] ]
 
        fArg:
            [ '&' ] ID [ init ]            // the optional '&' is for pass-by-expression, i.e. lazy evaluation, i.e. argument expression is implicitly wrapped in a function call that returns the evaluated expression. Note not allowed for return type.
           
      purity:
        'impure'
        'mutable'

  fBody:
      '->' [ NL ] rightExpr
      scope
     
expression:
  assign
  rightExpr
     
  assign:
      leftExpr [ NL ] assignop [ NLI ] rightExpr
       
      leftExpr:
        ID { [ NL ] memberRef }                // only a named reference, or its class properties, may be assigned to. This simplifies our grammar significantly. Since we are targetting pure programming, we discourage the assignment to a reference which is an unsaved return value-- because in pure programming we can only return a new instance and it thus has not been saved any where, thus would only be useful for impure, side-effect programming. Such impure programming can still be done (save a return value to a reference before assigning to it). Note, a method which inputs a 'void' can be called without '()', so semantic analysis should not allow assign to return value of such, nor its class properties.
        //conflicts with call below: '(' assign ')' { [ NL ] memberRef }+  // an assign has saved a reference in an ID, so we can assign to its class properties.
       
        memberRef:
            '.' [ NLI ] ID      // no [ NL ] after the operator, http://code.google.com/p/copute/issues/detail?id=31
     
      rightExpr:
        boolOr [ [ NL ] '?' [ NLI ] assign [ NL ] ':' [ NLI ] assign ]  // aka 'ternary' operator
 
        boolOr:
            boolAnd { [ NL ] '||' [ NLI ] boolAnd }
 
            boolAnd:
              bitOr { [ NL ] '&&' [ NLI ] bitOr }
 
              bitOr:
                  bitXor { [ NL ] '|' [ NLI ] bitXor }
 
                  bitXor:
                    bitAnd { [ NL ] '^' [ NLI ] bitAnd }
 
                    bitAnd:
                        equality { [ NL ] '&' [ NLI ] equality }
 
                        equality:
                          compare { [ NL ] equalityop [ NLI ] compare }
 
                          compare:
                              extrapolate { [ NL ] compareop [ NLI ] shift }
 
                              shift:
                                concat { [ NL ] shiftop [ NLI ] concat }
 
                                concat:
                                    add { [ NL ] '#' [ NLI ] add }
 
                                    add:
                                      multiply { addop [ NLI ] multiply }    // see NLPLUS and NLMINUS, we can't put a NL in front of addop, because NL also separates expr, and unary contains an addop on its left-side in prefixop
 
                                      multiply:
                                          unary { [ NL ] multiplyop [ NLI ] unary }
 
                                          unary:
                                            [ prefixop ] [ postfixop ] instance [ postfixop ]
                                           
                                            instance:
                                                primary { [ NL ] memberRef } [ callExpr ]    // Semantic analysis must determine if 'memberRef' and/or 'callExpr' is allowed on 'primary'. Also, a function call might not return an instance (i.e. 'void') for an impure function that has side-effects.
                                                'new' [ NL ] cDecl call
                                               
                                                primary:
                                                  ID
                                                  '(' [ NL ] expression [ NL ] ')'
                                                  '(' [ NL ] function [ NL ] ')'
                                                  switch
                                               
                                                callExpr:
                                                  call { callSuffix }

                                                  callSuffix:
                                                      call
                                                      [ NL ] memberRef
                                                     
                                                call:
                                                  '(' [ NL ] fParams [ NL ] ')'
                                                 
                                                  fParams:
                                                      expression [ [ NL ] ',' [ [ NL ] fParams ] ]
                                                     
                                                     
ifElse:
  'if' '(' rightExpr ')' then

  then:
      [ NLI ] expression                    // use NLI instead of NL, http://code.google.com/p/copute/issues/detail?id=28
      [ NL ] scope [ [ NL ] 'else' block ]  // if there is an 'else', force braces on the 'if', http://code.google.com/p/copute/issues/detail?id=21#c2

      block:
        [ NLI ] expression                  // use NLI instead of NL, http://code.google.com/p/copute/issues/detail?id=28
        scope
                                                     
switch:
  'switch' '(' [ NL ] expression [ NL ] ')' [ NL ] '{' [ NL ] { case } [ default ] '}'    // We force the '(' and ')' because, http://code.google.com/p/copute/issues/detail?id=30&can=1

  case:
      'case' rightExpr ':' [ NL ] sourcesOrEmpty [ NL ]    // allow empty case ';', so that user can do noop for specific cases without a default, to make sure all cases are coded
 
      sourcesOrEmpty:
        sources
        ';'
 
  default:
      'default' ':' [ NL ] sourcesOrEmpty [ NL ]
     

class:
  genre ID [ [ NL ] tArgList ] [ NL ] cDecl      // if INTERFACE, then ID must begin with "I[A-Z]", else "[A-HJ-Z][^A-Z]", http://copute.com/dev/docs/Copute/ref/class.html#Inheritance

anonyClass:
  genre [ [ NL ] funcArgs ] [ NL ] cDecl

  genre:
      'case'
      'class'
      'mixin'
      'interface'
     
  tArgList:
      '<' tArgs '>'
 
      tArgs:
        [ NL ] tArg [ [ NL ] ',' [ tArgs ] ]
 
        tArg:
            [ variance ] ID [ tArgList ] [ tConstrain ]      // the 'tArgList' is for a higher-kinded type parameter
 
            variance:
              '+'
              '-'
 
            tConstrain:
              subTypeOf [ NL ] type [ superTypeOf [ NL ] type ]
              superTypeOf [ NL ] type
 
                  subTypeOf:
                    ':'
 
                  superTypeOf:
                    '<:'
                 
  cDecl:
      [ inherit [ NL ] ] [ constructor [ NL ] ] cBody  // semantic analysis must not allow 'constructor' for 'interface' and 'mixin'
     
      inherit:
        'inherits' cTypes
       
      constructor:
        [ 'private' [ NL ] ] fDecl

        cTypes:
            [ NL ] cType [ [ NL ] ',' [ cTypes ] ]
 
            cType:
              ID [ tParamList ]  // ID is class
              anonyClass
 
              tParamList:
                  '<' types [ NL ] '>'

      cBody:
        '{' [ [ NL ] cMember { [ ',' ] [ NL ] cMember } ] [ NL ] '}'

        cMember:
            [ 'private' ] cMemberSuffix

            cMemberSuffix:
              cmBody
              class    // Note, this can be a CASE

              cmBody:
                  [ 'static' ] ID [ etters ] [ [ NL ] typeInit ] // this can be a 'CASE ID', when 'genre' is 'interface', because no ID without 'etters' in 'interface'
                  'case' ID

                  etters:
                    '(' access ',' access ')'    // The modifier that precedes ID must not be 'private'

                    access:
                        'public'
                        'new'
                        'private'


// Operator sets
prefixop:
  addop    // http://stackoverflow.com/questions/2624410/what-is-the-purpose-of-javas-unary-plus-operator
  NLPLUS  // http://code.google.com/p/copute/issues/detail?id=23, where this terminal will conflict with an NL or addop expected, otherwise process as PLUS...
  NLMINUS  // ...or MINUS
  '!'
  '~'
  TYPEOF  // can be used with type parametrization to fork functionality, although this is equivalent to overloading and/or using an case class, so I may deprecate this

postfixop:
  '++'
  '--'

multiplyop:
  '*'
  '/'
  '%'

addop:
  '+'
  '-'

shiftop:
  '<<'
  '>>'
  '>>>'

compareop:
//  '<'      // use MORE instead and flip operands, conflicts with sequence type ('tParamList')
  '>'
  '<='
  '>='

equalityop:
  '=='
  '!='
  ===        // compare the instance data (or overloaded), same as EQUAL for pass-by-value types
  !==        // compare the instance data (or overloaded), same as NOTEQUAL for pass-by-value types

assignop:
  '='
  '&='
  '|='
  '^='
  '*='
  '\='
  '%='
  '+='
  '-='
  '<<='
  '>>='
  '>>>='
  '#='

Yes, it’s true. I was there [in 1983]. See “a roomful of hackers with an innate distrust of hierarchy and a strong allergy to system designs with single-point vulnerability”. Our distrust extended to systems vulnerable to political single-point failures as well as technical ones.

Do you get it yet, Ms. Love? You rely on open-source software written by me and my peers for “day-to-day functionality” every day you touch the Internet or anything that talks to it. But you don’t see it, because we’ve done our job so well that our part of the infrastructure is almost invisible to you. You are free to make snotty remarks about our inability to meet user needs only because we have created for you the luxury of ignorance. And you are able to dismiss our concerns as hysteria only because more layers of ignorance lie between you and the long struggle we have waged against similar power grabs in the past

World Without Web...

...I’m going to sketch an all-too-plausible alternate history in which the World Wide Web never happened.

The divergence point for this history is in 1983-1984, when the leadership of DARPA lied through its teeth to Congress about who was being allowed access to the Internet. The pretense being maintained was that only direct affiliates of government-sponsored, authorized research programs were being allowed on. DARPA knew very well this wasn’t true; they had a broader vision of where the Internet might lead, one that wouldn’t be realized for another ten years. They viewed the yeasty, chaotic culture of casual use by all manner of ‘randoms’ (unauthorized people including, at the time, me) as what would later be called a technology incubator – a vast Petri dish from which amazing serendipities would spring in due time...

>Sounds like you like government after all.

Remember, I attribute the takeoff of the Internet to DARPA deliberately lying to its political masters. This happened precisely because DARPA’s leadership knew it was impossible within the incentives operating on governments for them to tolerate the ‘randoms’ or the results DARPA foresaw.

>Further, like most advocates of the state who say “if there was no government who would build roads?”

If you think this what-if qualifies me as an “advocate of the state”, you’re out of your fucking mind.

I don’t know what evolutionary path would have gotten a free market in telecomms to an Internet. I do know that we didn’t get to run that experiment, because there was a government-created telecomms monopoly firmly in place. Even after the AT&T divestiture our infrastructure retained the stamp of that monopoly in ways both large and small. We are just lucky that DARPA subverted the normal centralizing tendency of government at a crucial time.

>But I will point to the existance of the SF mailing list as evidence that, just as Eric says, the DARPA folks were lying about off-program uset of the Arpanet.

Heh. I’d bet that half the DARPA program monitors were on that list. Here, on information and belief, is how I think their reasoning went:

“This list is fun. It’s also an experiment in a novel mode of communication (most historians, including me, think it was the very first Internet mailing list). As such, it’s legitimately part of our research into the consequences of cheap, robust wide-area networking. And so is letting on all those college kids who don’t technically qualify under the program charter. But if we try to explain that at the Congressional hearings, we’re sure as shit going to get Proxmired.”

It was a reasonable fear. William Proxmire trashed a lot of immensely valuable research in the course of his political grandstanding. Once or twice he even apologized afterwards, but the damage had been done. I’ve had it pretty strongly hinted to me that certain of those responsible believed lying to Congress was less risky than telling the truth where Proxmire could get wind of it.

I suspect the Internet program managers were neither the first nor the last to make that choice. And be justified in making it.

Code:

interface IFunctor< Sub<T> : IFunctor<Sub,T>, T+ >
{
  map<A>        : (T -> A)        -> Sub<A>
}
// Functional programming (FP) paradigms are fundamentally about not repeating oneself.
// Functor enables the reuse of all functions of type, T -> A, to which we give the name "morphism functions".
//
// A functor has a 'map' method, which enables all morphism functions of type, T -> A,
// to operate on functors of type, Sub<T>, producing a result of type, Sub<A>.
// Conceptually, a functor maps all functions of type, T -> A, to functions of type, Sub<T> -> Sub<A>
//
// This enables the reuse of these morphism functions, without requiring specialized versions of type, Sub<T> -> Sub<A>.
// For example, if List<T> is functor, then a function of type, Int -> String, can convert a List<Int> into a List<String>.
// There is no need to code a specialized morphism function of type, List<Int> -> List<String>.
//
// A functor has some computation, data structure, or other form of state wrapped around the instance(s) of any type T.
// Thus all functions between unwrapped types are automatically lifted to functions between the wrapped types.
//
// The parametrized subtype, Sub<T>, has a 'map' method which returns an instance of the subtype, Sub<A>,
// where the type parameter T has been converted to a type A.
//
// The 'map' method inputs a function, T -> A,
// i.e. that function inputs a type T and returns a type A.
//
// Note that since 'map' is a method then it inputs 'this', so when viewed as a function,
// it has the type, Sub<T> -> (T -> A) -> Sub<A>.
//
// For example, given the input parameter to 'map' is a function of type, Int -> String,
// i.e. that inputs an integer and returns a string,
// then a (subtype of IFunctor that is a) list of integers, List<Int>,
// is converted to a list of strings, List<String>.
//
// Mapping is between the same subtype, Sub, i.e. Sub<T> -> Sub<A> and not Sub<T> -> Sub2<A>.
// This is because the subtype may not always be invertible (bijective)
// to the wrapped parametric type, T. For example, since Maybe<T>.none contains no instance of T
// (i.e. it can't be inverted to an unwrapped T), it is conceptually sensible to map it to an empty List<A>.
// However, there is no consistent model that will enable such a mapping and
// hold true in all general cases of destination subtypes.
//
// In category theory, a functor is a model of COMPOSABLE mappings between categories.
// In our case, each category is a concrete realization of the type, Sub<T>,
// i.e. the type parameter T is concrete type.
// Thus, our functor has a mapping from category Sub<T> to Sub<A>, given the morphism function, T -> A.
// A functor follows the laws that insure it is composable:
//    http://en.wikipedia.org/w/index.php?title=Functor&oldid=433685926#Definition
//      map( g ).map( f ) == map( \x -> f(g(x)) )      F(g) * F(f) == F( g * f )
//      u.map( \x -> x )  == u                          F(id)      == id



interface IApplicative< Sub<T> : IApplicative<Sub,T>, T+ > inherits IFunctor<Sub,T>
{
  static wrap<A> : A              -> Sub<A>
  apply<T, A>    : Sub<T -> A>    -> Sub<A>
}
// Read first the documentation for IFunctor.
//
// Conceptually, an applicative empowers any morphism function, which inputs unwrapped type(s),
// to operate on (an) applicative(s) of those type(s).
// Thus, specialized versions of morphism functions do not need to be written for each applicative subtype.
//
// Using the 'apply' method, a function of type, T -> A, which inputs type T and returns type A,
// can operate on an applicative of type Sub<T>, and return an applicative of type Sub<A>.
//
// Note that if the function inputs multiple parameters, then A will be the curried function type,
// e.g. if the function is of type, T -> B -> C, then the A in T -> A is of type, B -> C.
// Thus the example function would return a value of type C, from two applicative inputs--
// first of type Sub<T>, second of type Sub<B>.
//
// For example, a function of type, Int -> Int -> Int, which adds two integers and returns the result,
// can input two Maybe<Int> and return a Maybe<Int>.
// Thus, if either of the inputs is a Maybe<Int>.none (i.e. "null"), then 'apply' does not call the function
// and a Maybe<Int>.none is returned.
//
// The parametrized subtype of an applicative, Sub<_>, has a static 'wrap' method
// that constructs an instance of itself, Sub<A>,
// from an input argument which is an instance of type, A.
//
// Applicative is a functor that adds a mapping, 'apply', which inputs the morphism function, T -> A,
// wrapped in an instance of its subtype, Sub<T -> A>.
//
// Note that since 'apply' is a method then it inputs 'this', so when viewed as a function,
// it has the type, Sub<T> -> Sub<T -> A> -> Sub<A>.
//
// Wrapping the input morphism function enables multiple 'apply' to be chained,
// so that a multiple parameter morphism function,
// e.g. T -> B -> C -> D where the A in T -> A is of type B -> C -> D,
// can be distributed to multiple instances of applicative, e.g. Sub<T>, Sub<B>, Sub<C>.
// Without the such a model, the equivalent code is excessively verbose
// and must be specialized for each subtype, as shown in examples below, and also at this link:
//    http://en.wikibooks.org/wiki/Haskell/Applicative_Functors#Using_Applicative_Functors
//
// For example, given a morphism function of type, Int -> Int -> Int -> Int:
//    f : Int -> Int -> Int -> Int = \a, b, c -> a + (b * c)
// Apply this function to 3 lists, List( 1, 2, 3 ), List( 10 ), List( 6, 7 ), as follows:
//    List( 1, 2, 3 ).apply( List( 10 ).apply( List( 6, 7 ).apply( List.wrap( f ) )))
//    List( 1, 2, 3 ).apply( List( 10 ).apply( List( 6, 7 ).map( f ) ))
// IDEs should optionally allow entry and rendering as if 'apply' and 'map' are operators <*> and <<<
// (TODO: formalize Copute grammar for operator vs. method equivalents):
//    List( f ) <*> List( 6, 7 ) <*> List( 10 ) <*> List( 1, 2, 3 )
//    f <<< List( 6, 7 ) <*> List( 10 ) <*> List( 1, 2, 3 )
// The result is List( 16, 26, 36, 17, 27, 37 ).
//
// Each applicaion of 'apply' curries the function, f, with the elements of the list:
//    List.wrap( f ) == List( f )
//    List( 6, 7 ).apply( List( f ) ) == List( f(6), f(7) )
//    List( 10 ).apply( List( f(6), f(7) ) ) == List( f(6)(10), f(7)(10) )
//    List( 1, 2, 3 ).apply( List( f(6)(10), f(7)(10) ) ) == List( f(6)(10)(1), f(6)(10)(2), f(6)(10)(3), f(7)(10)(1), f(7)(10)(2), f(7)(10)(3) )
//    List( f(6)(10)(1), f(6)(10)(2), f(6)(10)(3), f(7)(10)(1), f(7)(10)(2), f(7)(10)(3) ) == List( 16, 26, 36, 17, 27, 37 )
//
// f is a function of type Int -> Int -> Int -> Int                  List( f )                        is type List<Int -> Int -> Int -> Int>
// f(6) is a curried function of type Int -> Int -> Int              List( f(6), f(7) )              is type List<Int -> Int -> Int>
// f(6)(10) or f(6,10) is a curried function of type Int -> Int      List( f(6)(10), f(7)(10) )      is type List<Int -> Int>
// f(6)(10)(1) or f(6,10,1) returns an Int with value 16            List( 16, 26, 36, 17, 27, 37 )  is type List<Int>
//
// The equivalent code without an applicative model is:
//    ref a = List( 6, 7 ), b = List( 10 ), c = List( 1, 2, 3 )
//    ref result = List(
//      f(a.head, b.head, c.head),
//      f(a.head, b.head, c.tail.head),
//      f(a.head, b.head, c.tail.tail.head)
//      f(a.tail.head, b.head, c.head),
//      f(a.tail.head, b.head, c.tail.head),
//      f(a.tail.head, b.head, c.tail.tail.head) )
//
// The applicative model expresses the semantics more clearly:
//    ref result = List( f ) <*> List( 6, 7 ) <*> List( 10 ) <*> List( 1, 2, 3 )
//
// The Maybe type can wrap the none case:
//    Maybe.wrap( f ) <*> Maybe.wrap( 3 ) <*> Maybe.wrap( 4 ) <*> Maybe.wrap( 5 ) == Maybe.wrap( 23 )
//    Maybe.wrap( f ) <*> Maybe.wrap( 3 ) <*> Maybe<Int>.none <*> Maybe.wrap( 5 ) == Maybe<Int>.none
//
// The equivalent code without an applicative model is:
//    ref a = Maybe.wrap( 3 ), b = Maybe.wrap( 4 ), c = Maybe.wrap( 5 ) // or b = Maybe<Int>.none
//    ref result = \ {
//      switch( a ) {
//          case none: return a
//          case is( ia ):
//            switch( b ) {
//                case none: return b
//                case is( ib ):
//                  switch( c ) {
//                      case none: return c
//                      case is( ic ): return Maybe.wrap( f(ia,ib,ic) )
//                  }
//            }
//      }
//    }()
//
// The above equivalent code is computationally more efficient than the applicative model,
// because the case 'none', can short-circuit the subsequent tests for case 'none'.
// Whereas, the applicative model tests for case 'none' on every 'apply' call, i.e. innermost 'apply' called first,
// and Maybe<Int>.none is returned (instead of for example Maybe.wrap( f(3)(4) )) to be input by the next 'apply':
//
//    c.apply( b.apply( a.apply( Maybe.wrap(f) )))
//
// In contrast, since IMonad.bind inputs an unwrapped morphism function that returns a type of Sub<A> instead of A,
// thus IMonad.bind are chained by nesting lamba functions, i.e. outermost bind called first,
// which can thus be short-circuited:
//
//    c.bind( \ic -> b.bind( \ib -> a.bind( \ia -> Maybe.wrap(f(ia,ib,ic)) )))
//
// However, this ability to short-circuit has the cost that IMonad does not generally compose:
//    The Essence of the Iterator Pattern, Gibbons & Oliveira, sec2.3 on pg 5, sec3 on pg 6, sec3.3 on pg 8
//    Applicative programming with effects, McBride & Paterson, sec5 on pg 8
//    http://blog.tmorris.net/monads-do-not-compose/
//
// I was originally incorrectly thinking that an empty list would conflict with the semantics of applicative:
//    http://goldwetrust.up-with.com/t112p150-computers#4294  (this link also contains an idea for avoiding exceptions with Nil)
// However, I now realize that an empty list is analgous to Maybe<T>.none,
// such that an empty list should be returned from chained 'apply'.
//
// Every subtype must fulfill the following laws from category theory.
//    The Essence of the Iterator Pattern, Gibbons & Oliveira, sec3 on pg 6 (laws insure any applicative expression can be converted to the canonical form)
//    Applicative programming with effects", McBride & Patterson, sec2 on pg 3
//    (i)  wrap id 'ap' u = u                                u.apply( wrap( \t -> t ) )                              == u
//    (ii)  wrap (*) 'ap' f 'ap' g 'ap' u = f 'ap' (g 'ap' u)  u.apply( g.apply( f.apply( wrap( \f,g,u -> f(g(u)) ))))  == u.apply( g ).apply( f )
//    (iii) wrap f 'ap' wrap x = wrap (f x)                    wrap( x ).apply( wrap(f) )                              == wrap( f(x) )
//    (iv)  u 'ap' wrap x = wrap (\f -> f x) 'ap' f            wrap( x ).apply( f )                                    == f.wrap( \f -> f(x) )



mixin Applicative< Sub<T> : Applicative<Sub,T>, T+ > inherits IApplicative<Sub,T>
{
  map = f -> apply( Sub.wrap(f) )
}
// Default implementation of IFunctor.map given an IApplicative.
//
// IFunctor.map has an input parameter f that is type, T -> A, thus Sub.wrap(f) returns type, Sub<T -> A>,
// and thus 'apply' returns type Sub<A>, which is the return type of IFunctor.map.



interface IMonad< Sub<T> : IMonad<Sub,T>, T+ > inherits IApplicative<Sub,T>
{
  bind<A>                              : (T -> Sub<A>) -> Sub<A>
  static join< M<A> : IMonad<M,A>, A >  : IMonad<_,M> -> M<A>      = nested -> nested.bind( \t -> t )
}
// Read first the documentation for IApplicative.
//
// Conceptually, monad enables morphism functions, T -> A, which operate on unwrapped types,
// to compose with functions, T -> Sub<A>, which return the wrapped subtype.
//
// Normal function composition means given function, f : A -> B, and function, g : T -> A,
// then we can write a composition function, h : (T -> A) -> (A -> B) -> T -> B = \g, f, x -> f( g(x) ),
// which inputs two functions and an instance of type T, then returns an instance of type B.
// Monad allows this composition where even if zero, one or both of the functions are instead,  f : A -> Sub<B>, or g : T -> Sub<A>.
//
// To gain insight into why monadic composition is useful, consider that each instance of the Maybe<T> monad,
// contains either an instance of T or the value 'none' (i.e. conceptually similar to 'null').
// Thus functions, g, that return Maybe<A> can be composed with functions, f, that input an A.
//    h : (T -> Maybe<A>) -> (A -> B) -> T -> B = \g, f, x -> g(x).map( f )
// Otherwise, we would create boilerplate to test the return value for the 'none' value, as follows.
//    h : (T -> Maybe<A>) -> (A -> B) -> T -> B = \g, f, x { t = g(x); -> t != Maybe<A>.none ? f(t) : t }
// But it isn't just the small amount of boilerplate that is avoided for the Maybe monad,
// but different boilerplate for each subtype of monad, some which might be more lengthy. e.g. the State monad.
// And with subtype specific boilerplate, the generalized IMonad interface couldn't be referred to in arguments and return values.
//    http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html
//
// Monad is an applicative model that adds a method 'bind',
// that inputs the morphism function, T -> Sub<A>, which returns Sub<A>.
//
// Functions which operate on unwrapped types, T -> A, can be input to 'map', or composed with the static 'wrap' method,
// and the composition function input to 'bind' (but 'map' might be more optimized).
//
// Note that since 'bind' is a method then it inputs 'this', so when viewed as a function,
// it has the type, Sub<T> -> (T -> Sub<A>) -> Sub<A>.
//
//
// Unlike applicative, a fully generalized composition of monads is not possible.
//    The Essence of the Iterator Pattern, Gibbons & Oliveira, sec2.3 on pg 5, sec3 on pg 6, sec3.3 on pg 8
//    Applicative programming with effects, McBride & Paterson, sec5 on pg 8
//    http://blog.tmorris.net/monads-do-not-compose/
// Because the monad is more powerful in that the outermost of a composition executes before innermost.
//    c.bind( \ic -> b.bind( \ib -> a.bind( \ia -> Maybe.wrap(f(ia,ib,ic)) )))
// Which is opposite of applicative.
//    c.apply( b.apply( a.apply( Maybe.wrap(f) )))
//
// Monad's 'bind' makes possible a 'join' method that flattens a "wrapping of a wrapping" to a wrapping.
// Imagine a container of container(s) of a type, e.g. List<List<T>>, flattened to a container of that type, e.g. List<T>.
//
// Every subtype must fulfill the following laws from category theory:
//    Comprehending Monads, Wadler, pg 3
//    Monad laws, Monads for functional programming, Wadler, sec3
//    The laws involving join, follow from the laws for a monoid, http://apocalisp.wordpress.com/2010/07/21/more-on-monoids-and-monads/
//    (i)  map id = id                        \t -> t.map( \u -> u )                    == \t -> t
//    (ii)  map (f * g) = map f * map g        i.map( \t -> f( g(t) ) )                  == i.map( \t -> g(t); ).map( \t -> f(t) )
//    (iii) map f * wrap = wrap * f            \t -> wrap( wrap(t) ).map( f )            == \t -> wrap( f( wrap(t) ) )
//    (iv)  map f * join = join * map (map f)  \t -> join( wrap( wrap(t) ) ).map( f )    == \t -> join( wrap( wrap(t) ).map( wrap(t).map(f) ) )
//    (I)  join * wrap = id                    \t -> join( wrap(t) )                    == \t -> t
//    (II)  join * map wrap = id                \t -> join( t.map( \u -> wrap(u) )        == \t -> t
//    (III) join * map join = join * join      \t -> join( t.map( \u -> join(u) )        == \t -> join( join(t) )



mixin Monad< Sub<T> : Monad<Sub<T>,T>, T+ > inherits IMonad<Sub,T>
{
  map                        = f -> bind( \t -> Sub.wrap( f(t) ) )
  apply                      = mf -> mf.bind( \f -> map(f) )
}
// Default implementation of IFunctor.map and IApplicative.apply given an IMonad.
//
// IFunctor.map has an input parameter f that is type, T -> A,
// thus the function, \t -> Sub.wrap( f(t) ), has type, T -> Sub<A>,
// and thus 'bind' returns type Sub<A>, which is the return type of 'map'.
//
// IApplicative.apply has an input parameter mf that is type, Sub<T -> A>,
// thus the function, \f -> map(f), has type, (T -> A) -> Sub<A>,
// because 'map' has the type, (T -> A) -> Sub<A>.
// Thus 'mf.bind' returns type Sub<A>, which is the return type of 'apply'.



interface IMState<S,T+> inherits Monad<IMState<S,_>,T>  // IMState<S,_> is partial type application, because IMonad expects Sub<T>, not Sub<T,S>. Scala's partial type application syntax is more verbose, see section 5 of "Generics of a Higher Kind", and: http://stackoverflow.com/questions/6247817/is-it-possible-to-curry-higher-kinded-types-in-scala/6248296#6248296
{
  m (public, const) : impure (S -> <(S,T)>)
  // Overload 'map' to support morphism functions that operate on state
  impure map<A>    : impure (<(S,T)> -> A) -> IMState<S,T>
}



interface IState<S,T+> inherits Monad<IState<S,_>,T>  // IState<S,_> is partial type application, because IMonad expects Sub<T>, not Sub<T,S>. Scala's partial type application syntax is more verbose, see section 5 of "Generics of a Higher Kind", and: http://stackoverflow.com/questions/6247817/is-it-possible-to-curry-higher-kinded-types-in-scala/6248296#6248296
{
  m (public, const) : (S -> <(S,T)>)
  // Overload 'map' to support morphism functions that operate on state
  map<A>        : (<(S,T)> -> <(S,A)>)    -> IState<S,T>
}



class MState<S,T+> inherits IMState<S,T>
  : (S -> <(S,T)>) = \m                        // <(S,T)> is a shortcut for Tuple2<S,T>
{
  m    = m
  wrap  = \t -> State<S,T>( \x -> <(x,t)> )
  bind  = \k -> State<S,T>( \x
      {
        <(y,b)> = m(x)                        // shortcut for, r : Tuple2 = m(x); y = r._0; b = r._1
        -> k(b).m(y)
      } )
  impure map<A>  :  impure (<(S,T)> -> A)  -> IMState<S,T>  = \k -> MState<S,T>( \x
      {
        <(y,b)> = m(x)
        -> <( y, k(y,b) )>  // 'k' may be impure if it modifies state referenced by 'y'
      } )
}



class State<S,T+> inherits IState<S,T>
  : (S -> <(S,T)>) = \m                        // <(S,T)> is a shortcut for Tuple2<S,T>
{
  m    = m
  wrap  = \t -> State<S,T>( \x -> <(x,t)> )
  bind  = \k -> State<S,T>( \x
      {
        <(y,b)> = m(x)                        // shortcut for, r : Tuple2 = m(x); y = r._0; b = r._1
        -> k(b).m(y)
      } )
  map<A>        : (<(S,T)> -> <(S,A)>)    -> IState<S,T>    = \k -> State<S,T>( \x -> k(m(x)) )    // 'k' is pure because it returns a copy of the (potentially modified) state
}
// Read first the documentation for IMonad.
//
// Conceptually, the state monad enables composition of morphism functions, T -> A,
// which do not operate on the wrapped state of type, S,
// with stateful morphism functions that operate on the tuple of the wrapped state, <(S,T)> -> <(S,A)>.
//
// <(S,T)> -> <(S,A)> is short-hand for Tuple2<S,T> -> Tuple2<S,A>,
// where TupleN is a convenient way of passing N instances around in one instance.
//
// Since the stateful morphisms input the wrapped state, the State.map method is used to compose them,
// instead of the 'bind' method. Note 'bind' is called by the default mixin implementation
// of Monad.apply.
//
// The state of the state monad is unbounded sequence of nested functions of type, S -> <(S,T)>.
// This enables 'map' (via its call of 'bind') to thread the state across morphism functions, T -> A,
// which do not operate on the state, S.
// This threading is equivalent to the normal function composition of these morphism functions.
// The benefit of using 'map' is that stateful morphism functions can also be mixed into the composition.
//
// When exclusively not composing impure morphism functions that operate on state (i.e. that do not return a copy of modified state),
// the state monadic composition of morphism functions,
// is not imperative and any order-dependency is no different conceptually than the
// normal composition of any pure functions:
//    http://goldwetrust.up-with.com/t112p180-computers#4434
//
// Method 'bind' inputs a morphism function that does not operate on state,
// and threads (bridges) the state across this function call,
// so the state is available to a nested 'bind', 'map', or 'apply'.
//
// Method 'map' is overloaded to support (both pure and impure) morphism functions that operate on state.
//
// See the example usage of the state monad in the documentation for ITraversable



interface IMonoid< Sub : IMonoid<Sub> >
{
  // An instance which is commutative as either operand to append.
  // http://en.wikipedia.org/wiki/Identity_element
  static identity      : Void -> Sub
  // An instance with the input instance appended.
  append              : Sub -> Sub
}
// Monoid has a default instance which is commutative over accumulation, and an associative accumulation function.
//
// Every subtype must fulfill the following laws from category theory:
//    append * identity = id                      \t -> t.append( identity )            == \t -> t
//    identity * append = id                      \t -> identity.append( t )            == \t -> t
//    (append a) append b = append (a append b)    \t,a,b -> t.append( a ).append( b )    == \t,a,b -> t.append( a.append( b ) )



interface IDualMonoid< Sub : IDualMonoid<Sub> > inherits IMonoid<Sub>
{
  prepend              : Sub -> Sub
}
// Dual of monoid appends in the opposite direction.



interface IMonoidHigherKind< Sub<T> : IMonoidHigherKind<Sub,T>, T+ > inherits IMonoid<Sub>
{
  static identity      : Void -> Sub<T>
  append<A <: T>      : Sub<A> -> Sub<A>
  append<A <: T>      : A -> Sub<A>
}
// Monoid parametrized on covariant T.



interface IDualMonoidHigherKind< Sub<T> : IDualMonoidHigherKind<Sub,T>, T+ > inherits IMonoidHigherKind<Sub,T>
{
  prepend<A <: T>      : Sub<A> -> Sub<A>
  prepend<A <: T>      : A -> Sub<A>
}
// Dual of monoid, parametrized on covariant T, appends in the opposite direction.



interface ITraversable< Sub<T> : ITraversable<Sub,T>, T+ >
{
  traverse< F<_> : IApplicative<F,_>, A >        : (T -> F<A>) -> F<Sub<A>>
  traverse< F<_> : IApplicative<F,_>, A, C >      : (Void -> C) -> (T -> C) -> (C -> T -> C) -> (T -> F<A>) -> F<Sub<A>>
  accumulate< M : IMonoid<M> >                    : (T -> M) -> M
  accumulate< M<A> : IMonoidHigherKind<M,A>, A >  : (T -> A) -> M<A> -> M<A>
  static dist< R<_> : ITraversable<R,_>, F<_> : IApplicative<F,_>, A >              : R<F<A>> -> F<R<A>> = nested -> nested.traverse( \t -> t )
  static concat< R<M> : ITraversable<R,M>, M : IMonoid<M> >                        : R<M> -> M          = nested -> nested.accumulate( \t -> t )
  static concat< R<M<A>> : ITraversable<R,M<A>>, M<A> : IMonoidHigherKind<M,A>, A > : R<M<A>> -> M<A>    = nested -> nested.accumulate( \t -> t )
}
// Conceptually, traverse iterates the contained instances of the parameter T,
// enabling both mapping and accumulating with a single pass of the iteration.
//
// Each contained instance of T is input to a mapping function, T -> F<A>, which returns an applicative, F.
// Note if A == T, then this mapping function is just IApplicative.wrap.
// These applicative are accumulated by a two parameter function, by employing the applicative model of function application.
// Since traversable might contain only zero or one instances of T,
// accumulation functions 'identity' and 'lift', which respectively input zero and one parameters, are also required.
//
// In Haskell, see [1] (but note 'accum' replaces 'f', added 'identity' and 'lift' parameters to generalize it):
//    traverseList : Applicative m => (() -> c) -> (b -> c) -> (c -> b -> c) -> (a -> m b) -> [a] -> m c
//    traverseList identity lift accum map [] = pure identity
//    traverseList identity lift accum map (head:[]) = pure (lift head)
//    traverseList identity lift accum map (head:tail) = (pure accum) <*> (traverse identity lift accum map tail) <*> (map head)
//
// In Copute, where traversable (which is a list in the Haskell example) is generalized to IHeadable:
//    traverse = \identity, lift, accum, map
//      {
//          if( head == Maybe<T>.none )
//            -> F.wrap( identity )
//          else if( tail == Maybe<T>.none )
//            -> F.wrap( lift(head) )
//          else
//            -> traverse( identity, lift, accum, map, tail ).apply( map( head ).apply( F.wrap(accum) ))  // F.wrap(accum) <*> traverse( identity, lift, accum, map, tail ) <*> map( head )
//      }
//
// Thus 'map' lifts the first contained instance 'head' to an applicative,
// which is input to the second parameter of 'accum' using the applicative model of function application.
// This is repeated recursively on 'tail', thus 'accum' inputs its own output type as its first parameter.
// Thus the return type is the applicative parametrized on the output type of 'accum'.
//
// We have generalized the traverse previously proposed in literature (see [1]),
// so that it possible to map with no-op accumulation function, or vice versa.
// Also our generalization allows an accumulation function to map the output container type.
// The Haskell example in the literature is obtained from our generalization as follows.
//    traverseList f list = traverseList [] (\x -> [x]) (:) f list
//
// Thus traverse distributes a function over each T, and returns the Applicative of Traversable,
// instead of Traversable of Applicative, as IFunctor.map would do.
//
// Thus traverse combines the IFunctor.map and ITraversable.dist into a single walk of T.
//
// State monad can be composed with traverse to fold the container into any state type.
//    traverse<IState,String>( \t -> State<Int,String>( \x -> <(x+1,t)> )).m(0) == <(count, ITraversable<_,String>)> // count a collection of String and create a new copy of the collection String
//    traverse<IState,Int>( \t -> State<Int,Int>( \x -> <(x+1,t.toInt)> )).m(0) == <(count, ITraversable<_,Int>)>    // count a collection of String and map to collection of Int
//    traverse<IState,Int>( \x -> 0, \x -> 0, \x -> 0, \t -> State<Int,Int>( \x -> <(x+1,0)> )).m(0) == <(count, 0)> // count a collection of String, without creating a copy of the collection
//
// References:
//    [1] Traversing data structures, Applicative programming with effects, McBride & Paterson, sec3 on pg 6
//    Idiomatic traversal, The Essence of the Iterator Pattern, Gibbons & Oliveira, sec3.4 on pg 8



mixin Traverse< Sub<T> : Traverse<Sub,T>, T+ > inherits ITraversable<Sub,T>, IMonoidHigherKind<Sub,T>, IHeadable
{
  traverse = f ->
  {
      if( isA<IHead> )
        -> f( head ).apply( tail.traverse(f).apply( F.wrap( append ) ) )
      else
        -> F.wrap( identity )
  }
}
// Default implementation of ITraversable.traverse, where given IMonoidHigherKind and IHeadable.
//
// See "traverse f (x : xs) = [ (:) (f x) (traverse f xs) ]" in Section 3 Traversing data structures, Applicative programming with effects, McBride and Paterson
//    x is head,
//    xs is tail,
//    (f x) has type F<A>,
//    (traverse f xs) has type F<Sub<A>>,
//    (:) is IMonoidHigherKind.append which has type Sub<A> -> A -> Sub<A>,
//    and inside the brackets [ and ] implies F.wrap( (:) ) and F.apply between each operand as explained on page 4.



mixin Accumulate< Sub<T> : Accumulate<Sub,T>, T+ > inherits ITraversable<Sub,T>, IHeadable
{
  accumulate = f ->
  {
      if( isA<IHead> )
        -> f( head ).append( tail.accumulate(f) )
      else
        -> M.identity
  }

  accumulate = \f, start ->
  {
      if( isA<IHead> )
        -> tail.accumulate( f, start.append( f(head) ) )
      else
        -> start
  }
}
// Default implementation of ITraversable.accumulate, where given IHeadable.

Code:

sources:
  { source }+
 
  source:
      class
      reference
      expression
      ifElse        // TODO: move this to 'primary' and change 'then' to use 'exprSansIfelse' instead of 'expression', and add 'else' to that line
     
  scope:
      '{' [ NL ] sources [ NL ] '}'
     
reference:
  [ refType ] ID typeInit    // without refType, defaults to 'cref' for pass-by-reference, and 'var' for pass-by-value, instances
  refType ID init            // TODO: remove this once we are ready to do type inference for assignment expression, see comment for //int below
 
  refType:
      'const'        // the instance can not be modified, regardless if it is pass-by-reference or pass-by-value
      'ref'          // the reference can be modified to point to a different instance, applies only to pass-by-reference instances
      'const' 'ref'  // combines the above meanings, note the reference is not constant.
      'var'          // 'const' 'var' is not allowed because has same meaning as 'const'
      'cref'        // 'const' 'cref' is not allowed because has same meaning as 'const'

  typeInit:
      : nfType [ [ NL ] typeInit2 ]  // init is optional if cType has a default constructor
      tArgList [ NL ] ':' fType [ NL ] '=' [ NL ] function
      //init        when refType is not specified, this is already in the grammar as the assignment expression. Disambiguate from assignment when ID is not already declared. Note this means a typo on ID will silently fail assignment and create a reference that is never accessed (so maybe we can detect on compilation and error). To hide an ID of same name in outer scope, then refType must be specified.

  init:
      '=' [ NL ] rightExpr
     
      typeInit2:
        init
        nextType [ NL ] '=' [ NL ] function
       
      nfType:
        cType          // include standard classes for the builtin types, Int, Float, String, Bool
       
      fType:
        nfType [ NL ] nextType
        fType2
     
        fType2:
            '(' fType ')' [ NL ] nextType
            'void' [ NL ] '->' [ NL ] xtype  // 'void' not an instance reference type, thus can not be a class, only allowed as a single argument or return type
       
        xtype:
            nfType
            '(' fType ')'

        type:
            nfType [ [ NL ] nextType ]
            fType2

        nextType:
            '->' [ NL ] xtype [ [ NL ] nextType ]
            '->' [ NL ] 'void'            // 'void' not an instance reference type, thus can not be a class, only allowed as a single argument or return type

function:
  fDecl [ NL ] fBody

  fDecl:
      [ purity ] '\' [ fArgs ]
     
      fArgs:
        fArg [ [ NL ] ',' [ [ NL ] fArgs ] ]
 
        fArg:
            [ '&' ] ID [ init ]            // the optional '&' is for pass-by-expression, i.e. lazy evaluation, i.e. argument expression is implicitly wrapped in a function call that returns the evaluated expression. Note not allowed for return type.
           
      purity:
        'impure'
        'mutable'

  fBody:
      '->' [ NL ] rightExpr
      scope
     
expression:
  assign
  rightExpr
     
  assign:
      leftExpr [ NL ] assignop [ NLI ] rightExpr
       
      leftExpr:
        ID { [ NL ] memberRef }                // only a named reference, or its class properties, may be assigned to. This simplifies our grammar significantly. Since we are targetting pure programming, we discourage the assignment to a reference which is an unsaved return value-- because in pure programming we can only return a new instance and it thus has not been saved any where, thus would only be useful for impure, side-effect programming. Such impure programming can still be done (save a return value to a reference before assigning to it). Note, a method which inputs a 'void' can be called without '()', so semantic analysis should not allow assign to return value of such, nor its class properties.
        //conflicts with call below: '(' assign ')' { [ NL ] memberRef }+  // an assign has saved a reference in an ID, so we can assign to its class properties.
       
        memberRef:
            '.' [ NLI ] ID      // no [ NL ] after the operator, http://code.google.com/p/copute/issues/detail?id=31
     
      rightExpr:
        boolOr [ [ NL ] '?' [ NLI ] assign [ NL ] ':' [ NLI ] assign ]  // aka 'ternary' operator
 
        boolOr:
            boolAnd { [ NL ] '||' [ NLI ] boolAnd }
 
            boolAnd:
              bitOr { [ NL ] '&&' [ NLI ] bitOr }
 
              bitOr:
                  bitXor { [ NL ] '|' [ NLI ] bitXor }
 
                  bitXor:
                    bitAnd { [ NL ] '^' [ NLI ] bitAnd }
 
                    bitAnd:
                        equality { [ NL ] '&' [ NLI ] equality }
 
                        equality:
                          compare { [ NL ] equalityop [ NLI ] compare }
 
                          compare:
                              extrapolate { [ NL ] compareop [ NLI ] shift }
 
                              shift:
                                concat { [ NL ] shiftop [ NLI ] concat }
 
                                concat:
                                    add { [ NL ] '#' [ NLI ] add }
 
                                    add:
                                      multiply { addop [ NLI ] multiply }    // see NLPLUS and NLMINUS, we can't put a NL in front of addop, because NL also separates expr, and unary contains an addop on its left-side in prefixop
 
                                      multiply:
                                          unary { [ NL ] multiplyop [ NLI ] unary }
 
                                          unary:
                                            [ prefixop ] [ postfixop ] instance [ postfixop ]
                                           
                                            instance:
                                                primary { [ NL ] memberRef } [ callExpr ]    // Semantic analysis must determine if 'memberRef' and/or 'callExpr' is allowed on 'primary'. Also, a function call might not return an instance (i.e. 'void') for an impure function that has side-effects.
                                                'new' [ NL ] cDecl call
                                               
                                                primary:
                                                  ID
                                                  '(' [ NL ] expression [ NL ] ')'
                                                  '(' [ NL ] function [ NL ] ')'
                                                  switch
                                               
                                                callExpr:
                                                  call { callSuffix }

                                                  callSuffix:
                                                      call
                                                      [ NL ] memberRef
                                                     
                                                call:
                                                  '(' [ NL ] fParams [ NL ] ')'
                                                 
                                                  fParams:
                                                      expression [ [ NL ] ',' [ [ NL ] fParams ] ]
                                                     
                                                     
ifElse:
  'if' '(' rightExpr ')' then

  then:
      [ NLI ] expression                    // use NLI instead of NL, http://code.google.com/p/copute/issues/detail?id=28
      [ NL ] scope [ [ NL ] 'else' block ]  // if there is an 'else', force braces on the 'if', http://code.google.com/p/copute/issues/detail?id=21#c2

      block:
        [ NLI ] expression                  // use NLI instead of NL, http://code.google.com/p/copute/issues/detail?id=28
        scope
                                                     
switch:
  'switch' '(' [ NL ] expression [ NL ] ')' [ NL ] '{' [ NL ] { case } [ default ] '}'    // We force the '(' and ')' because, http://code.google.com/p/copute/issues/detail?id=30&can=1

  case:
      'case' rightExpr ':' [ NL ] sourcesOrEmpty [ NL ]    // allow empty case ';', so that user can do noop for specific cases without a default, to make sure all cases are coded
 
      sourcesOrEmpty:
        sources
        ';'
 
  default:
      'default' ':' [ NL ] sourcesOrEmpty [ NL ]
     

class:
  genre ID [ [ NL ] tArgList ] [ NL ] cDecl      // if INTERFACE, then ID must begin with "I[A-Z]", else "[A-HJ-Z][^A-Z]", http://copute.com/dev/docs/Copute/ref/class.html#Inheritance

anonyClass:
  genre [ [ NL ] funcArgs ] [ NL ] cDecl

  genre:
      'case'
      'class'
      'mixin'
      'interface'
     
  tArgList:
      '<' tArgs '>'
 
      tArgs:
        [ NL ] tArg [ [ NL ] ',' [ tArgs ] ]
 
        tArg:
            [ variance ] ID [ tArgList ] [ tConstrain ]      // the 'tArgList' is for a higher-kinded type parameter
 
            variance:
              '+'
              '-'
 
            tConstrain:
              subTypeOf [ NL ] type [ superTypeOf [ NL ] type ]
              superTypeOf [ NL ] type
 
                  subTypeOf:
                    ':'
 
                  superTypeOf:
                    '<:'
                 
  cDecl:
      [ inherit [ NL ] ] [ constructor [ NL ] ] cBody  // semantic analysis must not allow 'constructor' for 'interface' and 'mixin'
     
      inherit:
        'inherits' cTypes
       
      constructor:
        [ 'private' [ NL ] ] ':' nfType [ NL ] [ nextType [ NL ] ] '=' [ NL ] fDecl

        cTypes:
            [ NL ] cType [ [ NL ] ',' [ cTypes ] ]
 
            cType:
              ID [ tParamList ]  // ID is class
              anonyClass
 
              tParamList:
                  '<' types [ NL ] '>'

      cBody:
        '{' [ [ NL ] cMember { [ ',' ] [ NL ] cMember } ] [ NL ] '}'

        cMember:
            [ 'private' ] cMemberSuffix

            cMemberSuffix:
              cmBody
              class    // Note, this can be a CASE

              cmBody:
                  [ 'static' ] ID [ etters ] [ [ NL ] typeInit ] // this can be a 'CASE ID', when 'genre' is 'interface', because no ID without 'etters' in 'interface'
                  'case' ID

                  etters:
                    '(' access ',' access ')'    // The modifier that precedes ID must not be 'private'

                    access:
                        'public'
                        'new'
                        'private'


// Operator sets
prefixop:
  addop    // http://stackoverflow.com/questions/2624410/what-is-the-purpose-of-javas-unary-plus-operator
  NLPLUS  // http://code.google.com/p/copute/issues/detail?id=23, where this terminal will conflict with an NL or addop expected, otherwise process as PLUS...
  NLMINUS  // ...or MINUS
  '!'
  '~'
  TYPEOF  // can be used with type parametrization to fork functionality, although this is equivalent to overloading and/or using an case class, so I may deprecate this

postfixop:
  '++'
  '--'

multiplyop:
  '*'
  '/'
  '%'

addop:
  '+'
  '-'

shiftop:
  '<<'
  '>>'
  '>>>'

compareop:
//  '<'      // use MORE instead and flip operands, conflicts with sequence type ('tParamList')
  '>'
  '<='
  '>='

equalityop:
  '=='
  '!='
  ===        // compare the instance data (or overloaded), same as EQUAL for pass-by-value types
  !==        // compare the instance data (or overloaded), same as NOTEQUAL for pass-by-value types

assignop:
  '='
  '&='
  '|='
  '^='
  '*='
  '\='
  '%='
  '+='
  '-='
  '<<='
  '>>='
  '>>>='
  '#='

...enables composition of functions over a large, sparse (even infinite), or diverse data space without conflating the implementation of the granularity on the space[4], e.g. the imperative example could not do logical recursion on fibs() for list-granularity.

[4]John Hughes (1984). "Why Functional Programming Matters" (¶8 §4, "Glueing Programs Together")