Swarm Final Report A Cellular Programming Language Team Epidemic Rajesh Ramakrishnan rr2318 columbia edu Jason Gluckman jbg2113 columbia edu Thomas Chau tc2165 columbia edu Greg Bramble gmb2106 columbia edu Programming Languages and Translators Fall 2007 Prof Stephen Edwards Table of Contents White Paper 4 Abstract 4 Motivation 4 Goals 4 Language Tutorial 5 What is a swarm 5 What is Swarm 5 A Full Example 6 Reference Manual 8 Introduction 8 Model of Computation 8 The Cell 9 The Facet 9 Binding 10 Lexical Conventions 10 Comments 10 Identifiers 10 Special Semantics 10 Primitive data cells 11 Main Cell 11 Meaning of Identifiers 11 Predefined Cells 12 Math cells 12 Comparison Cells 12 Input Output Cells 13 Derived Cells 14 Conversions 14 Declarations 14 Statements 14 Binding Operators 15 Direct Bind 15 Cross Bind 15 Chaining 15 Execution Flow 16 Scope and Linkage 16 Project Plan 17 Programming Style Guide 17 Project Timeline 17 Software Development Environment 18 2 Roles and Responsibilities 18 Project Log 18 Architecture Design 19 Testing Plan 21 Simple Test Cases 21 Conway s Game of Life fully implemented 23 Lessons Learned 25 Gregory Bramble 25 Thomas Chau 25 Jason Gluckman 25 Rajesh Ramakrishnan 25 Appendix Grammar 26 Appendix B Source Code 28 Repository Details 28 Code Listing 28 The Lexer Parser Walker and Main 28 Binds Facets Cells 35 Built in and Special Cells 48 Intermediate Representation Files 67 3 White Paper Abstract Swarm is a functional dataflow language aimed at building simulations Its programs are represented by directed graphs of cells Cells the basic functional unit perform computation by responding to particular sets of stimuli and propagate reactions to their neighbors To achieve a more intricate machine a programmer must compose primitive cells into more complex ones which in turn may be composed into yet larger units Motivation Everything in the world behaves in a cellular manner participating in vast interactions in which units feel each others influences and emit their own For example by universally speaking the language of electromagnetism atoms compose many interesting molecules These complexes then compose themselves into larger structures giving rise to cells The cells on the next order of magnitude act in concert and unite themselves by circulatory networks Finally humans too interact in a broad social framework and construct organizations to handle mass action While much reductionist work has been done to probe basic properties of these systems constituents important applications in biology and social science rely on understanding aggregate behavior in general Fortunately the current trends in hardware are beginning to meet the needs of such systems where complexity arises from the synergy of many parallel elements The days of the single processor are becoming history They were characterized by programs which were essentially lists of instructions to be processed sequentially Nearly all high level languages in existence were written for and conceptually constrained by this paradigm Even object oriented programming whose idea was to group instructions as more distinct entities is firmly implanted in the original paradigm While objects maintain their own states they are nonetheless are filled with functions that must execute and return before the main function can continue The OO paradigm more resembles a guideline for how to organize folders than a break from the procedural style that preceded it As a consequence we face a software crisis in which traditional languages have failed to capture parallel computation We ask ourselves how can we break away and write code to exploit new multiple processor technology Goals The goal of Swarm is to allow a programmer to explore emergent phenomena conveniently But even more importantly Swarm aims to establish a platform on which a programmer can write code that parallelizes naturally Swarm s style is declarative capturing the computation in a manner similar to that of functional languages Its programs rather than executing operations imperatively define the juxtaposition of data and functionality explicitly Swarm is a metalanguage whose operators perform highlevel manipulations of the superstructure of a network of functional units Swarm operators when executed link together these functional units the cells which provide conventional functionality 4 Language Tutorial What is a swarm If you have ever observed ants marching in and out of a nest you might have been reminded of a highway buzzing with traffic To Iain D Couzin such a comparison is a cruel insult to the ants Americans spend a 3 7 billion hours a year in congested traffic But you will never see ants stuck in gridlock Army ants which Dr Couzin has spent much time observing in Panama are particularly good at moving in swarms If they have to travel over a depression in the ground they erect bridges so that they can proceed as quickly as possible They build the bridges with their living bodies said Dr Couzin a mathematical biologist at Princeton University and the University of Oxford They build them up if they re required and they dissolve if they re not being used The reason may be that the ants have had a lot more time to adapt to living in big groups We haven t evolved in the societies we currently live in Dr Couzin said By studying army ants as well as birds fish locusts and other swarming animals Dr Couzin and his colleagues are starting to discover simple rules that allow swarms to work so well Those rules allow thousands of relatively simple animals to form a collective brain able to make decisions and move like a single organism from the New York Times November 13 2007 What is Swarm Swarm is a functional programming language that attempts to capture the idea from the above article Swarm consists of three basic ideas whose combination results in very powerful Swarm simulations These three ideas are cells facets and binds To understand these three basic ideas which is the goal of this tutorial we will look at a simple program that prints Hello World to output STRLIT Hello world SOUT MAIN The above code constructs a STR cell which is a built in cell with the value Hello world The out facet of the STR cell is bound to the IN facet of the SOUT also predefined cell The entire cell structure is specified between the brackets and it is defined as the MAIN cell The MAIN cell is a special cell which the compiler recognizes as the place to begin execution
View Full Document
Unlocking...