`
          Alma Mater Studiorum · Universita di Bologna
                          Campus di Cesena
                     Scuola di Ingegneria e Architettura
            Corso di Laurea Magistrale in Ingegneria e Scienze Informatiche
          Aggregate Programming in Scala:
           a Core Library and Actor-Based
                Platform for Distributed
                  Computational Fields
                              Tesi in
        Ingegneria dei Sistemi Software Adattativi Complessi
       Relatore:                              Presentata da:
       Prof. MIRKO VIROLI               ROBERTOCASADEI
                     Anno Accademico 2014-2015
                            Sessione III
                     Contents
                     Abstract (italiano)                                                                       i
                     Abstract                                                                                iii
                     Introduction                                                                             v
                     I   Background: Scala for Library Development                                            1
                     1 Advanced Scala Features                                                                3
                        1.1   The Scala programming language . . . . . . . . . . . . . . . . . . .            3
                        1.2   Onobject-oriented programming and traits . . . . . . . . . . . . . .            4
                              1.2.1   OOPinScala: a quick tour of the basics . . . . . . . . . . .            4
                              1.2.2   Traits   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    7
                              1.2.3   Class construction and linearisation . . . . . . . . . . . . . .        9
                              1.2.4   Traits: member overriding and super resolution . . . . . . .           10
                              1.2.5   Trait instantiation, refinement, early definitions . . . . . . .         11
                        1.3   The Scala type system . . . . . . . . . . . . . . . . . . . . . . . . .        12
                              1.3.1   Some preparatory definitions . . . . . . . . . . . . . . . . . .        12
                              1.3.2   Advanced types . . . . . . . . . . . . . . . . . . . . . . . . .       13
                        1.4   Generic programming in Scala . . . . . . . . . . . . . . . . . . . . .         16
                              1.4.1   Type parameters . . . . . . . . . . . . . . . . . . . . . . . .        17
                              1.4.2   Type bounds (bounded quantification) . . . . . . . . . . . .            17
                              1.4.3   Type variance . . . . . . . . . . . . . . . . . . . . . . . . . .      18
                              1.4.4   Abstract types vs. type parameters . . . . . . . . . . . . . .         20
                        1.5   Implicits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    21
                              1.5.1   Implicit scope . . . . . . . . . . . . . . . . . . . . . . . . . .     22
                       CONTENTS
                                1.5.2    Implicit classes   . . . . . . . . . . . . . . . . . . . . . . . . .  24
                                1.5.3    More on implicits . . . . . . . . . . . . . . . . . . . . . . . .     25
                       2 Advanced Scala Techniques                                                             29
                           2.1  “Pimp my library” pattern . . . . . . . . . . . . . . . . . . . . . . .        29
                           2.2  Type classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     31
                           2.3  Component modelling and implementation . . . . . . . . . . . . . .             32
                           2.4  Cake Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       35
                           2.5  Family polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . .        38
                           2.6  Internal DSL development . . . . . . . . . . . . . . . . . . . . . . .         41
                                2.6.1    On syntactic sugar . . . . . . . . . . . . . . . . . . . . . . .      41
                                2.6.2    On associativity and precedence . . . . . . . . . . . . . . . .       43
                                2.6.3    ”Dynamic” features . . . . . . . . . . . . . . . . . . . . . . .      44
                                2.6.4    Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . .      44
                       II    Background: Aggregate Programming                                                47
                       3 Space-Time Programming and Spatial Computing                                          49
                           3.1  Motivation: context and issues . . . . . . . . . . . . . . . . . . . . .       49
                                3.1.1    Distributed computing scenarios . . . . . . . . . . . . . . . .       50
                                3.1.2    Key issues and unsuitableness of traditional approaches . . .         51
                           3.2  Spatial computing . . . . . . . . . . . . . . . . . . . . . . . . . . . .      54
                                3.2.1    Space-oriented computation . . . . . . . . . . . . . . . . . .        54
                                3.2.2    Defining spatial computing (as space-time programming) . .             55
                                3.2.3    Analytical framework . . . . . . . . . . . . . . . . . . . . . .      56
                                3.2.4    Discrete vs. continuous space-time       . . . . . . . . . . . . . .  57
                       4 Field Calculus                                                                        59
                           4.1  Computational fields . . . . . . . . . . . . . . . . . . . . . . . . . .        59
                           4.2  Field calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     60
                                4.2.1    Basis set of operators . . . . . . . . . . . . . . . . . . . . . .    60
                                4.2.2    Higher-Order Field Calculus (HOFC) . . . . . . . . . . . . .          61
                                                                                                 CONTENTS
                              4.2.3   Operational semantics . . . . . . . . . . . . . . . . . . . . .        61
                              4.2.4   Case study: Protelis      . . . . . . . . . . . . . . . . . . . . . .  67
                     5 Aggregate Programming                                                                 69
                        5.1   From device to aggregate view . . . . . . . . . . . . . . . . . . . . .        69
                        5.2   The aggregate programming stack . . . . . . . . . . . . . . . . . . .          70
                              5.2.1   Composable self-organisation        . . . . . . . . . . . . . . . . .  71
                     III    scafi: Development                                                              75
                     6 Analysis                                                                              77
                        6.1   Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       77
                              6.1.1   Field calculus . . . . . . . . . . . . . . . . . . . . . . . . . .     78
                              6.1.2   Aggregate programming platform . . . . . . . . . . . . . . .           78
                        6.2   Requirement analysis . . . . . . . . . . . . . . . . . . . . . . . . . .       79
                              6.2.1   Field calculus – DSL and VM . . . . . . . . . . . . . . . . .          79
                              6.2.2   Aggregate programming systems           . . . . . . . . . . . . . . .  80
                        6.3   Problem analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .       83
                              6.3.1   Field calculus DSL: embedding within Scala . . . . . . . . .           83
                        6.4   Abstraction gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      85
                              6.4.1   Distributed Platform . . . . . . . . . . . . . . . . . . . . . .       85
                     7 Design                                                                                87
                        7.1   Design architecture . . . . . . . . . . . . . . . . . . . . . . . . . . .      88
                              7.1.1   scafi DSL and VM . . . . . . . . . . . . . . . . . . . . . .           88
                              7.1.2   Spatial abstraction . . . . . . . . . . . . . . . . . . . . . . .      89
                              7.1.3   Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . .      91
                              7.1.4   Distributed platform . . . . . . . . . . . . . . . . . . . . . .       92
                        7.2   Actor platform design       . . . . . . . . . . . . . . . . . . . . . . . . .  94
                              7.2.1   System design . . . . . . . . . . . . . . . . . . . . . . . . . .      94
                              7.2.2   Server-based actor platform . . . . . . . . . . . . . . . . . .        96
                              7.2.3   Peer-to-peer actor platform       . . . . . . . . . . . . . . . . . .  97