Programming in Star

By Francis McCabe

Star is a new programming language that is oriented to producing readable, accurate, scalable and performant applications. Readability involves not only using clear keywords and simple semantics; but only means extensibility: the syntax of Star can be extended to allow you to incorporate notations that more closely mirror your requirements.

Although functional programming has a reputation of arcane complexity and poor performance, the reality does not need to be either. What is undoubtably true is that there is a lot more to functional programming than is commonly found in todays main-stream languages: the formalism allows for a richer programming experience.

This book is a gentlest far-reaching introduction to the language. It starts with a significant amount of material on functional programming and continues onward to cover more advanced topics such as concurrency, agent-oriented programming and building domain specific languages.

• Language: English
• Publisher: Francis McCabe
• Release date: Jan 6, 2016
• ISBN: 9781311268655

Francis McCabe

Frank McCabe is a Senior Architect at Instart Logic Inc. Educated in England at Manchester University and Imperial College he has been involved in many research areas, in Europe, Japan and in the US. In the 1980's he co-founded a small startup LPA that developed logic programming solutions for many thousands of customers. During the 1990's he was active in the European scene for multi-agent systems. He participated in several European research projects. In the 2000's, he was active in Standard Settings Organizations (including W3C) focussing on areas such as the architecture of Service Ecosystems, Inter-agent communication, Java interfaces, Web services and Business Process Modeling Language. Recently he has been working on a new programming language – called Star – that aims to combine modern concepts from functional programming, best practices for software engineering and to permit straightforward extensibility. Star is a multi-paradigm language that can equally well tackle intensive real-time calculations and complex AI planning tasks such as scheduling the flow of material through a factory.

Book preview

Programming in Star

By Francis McCabe

Copyright 2016 Francis McCabe

Smashwords Edition

ISBN: 9781311268655

Table of Contents

Why Be a Star Programmer?

Programming has Changed

Real-time is normal time

Programming Safely and Effectively

This Train is Leaving the Station

Is Star for you?

If You Are Already a Functional Programmer

If You Are Already a Java (or C#, or C++) Programmer

Technology

Design Goals for Star

About this book

Getting hold of Star

Typographical Conventions

Acknowledgements

A Tour of Star

A First Star Program

Texture

Types

Rules

Patterns

Semi-colons are optional

Packages

Worksheets

String Interpolation

Types, More Types and Even More Types

Nominative Types

Optional Values

The Flavors of Equality

Quantified Types

A Tale of Three Loops

A Functional Loop

A Totalizer Query

The Homunculus in the Machine

Contracts and Constraints

Implementing Contracts

Coercion, not Casting

There is More

Functional Programming

What is Functional Programming?

Basics

Patterns

Order of Evaluation

Algebraic Data Types

Functions as Values

Functions and Closures

Let Binding Environments

Generic Programs

Generic Types

Generic Functions

Going Further

Going Even Further

Polymorphic Arithmetic

A Word About Type Inference

Are We There Yet?

Collections

Sequence Notation

Types and Sequence Notation

The Sequence Contract

Sequence Patterns

Notation and Contract-Based Semantics

Indexing

The indexable Contract

Tentative Computation

Adding and Removing Elements From a Collection

The Index Notation

Implementing Indexing

Index Slices

Doing Stuff With Collections

Filtering With filter

The Sieve of Erastosthenese

Mapping to Make New Collections

Compressing Collections With a Fold

Iteration

Queries

Satisfaction

Query Quantifiers

Types of Collection

The cons Type

The list Type

The dictionary Type

The Set Type

The range Type

Queries and Maps for Statistical Purposes

Summary

Boiling the Ocean

Packages and Worksheets

Package

The main Program

Worksheet

Importing Packages

Private Imports

Code Products

Code Repository

Universal Resource Identifier

Transducer

Standard URI Schemes

Package URIs

Catalogs

Existentialism

Type Variables and their Kind

Existential Types

Use and Evidence

Using Existentially Quantified Types

Abstract Data Types

Opening Up

Injection

Extensible Types

Phew

Concurrency

Tasks

The Value of a Task

Getting the value more than once

Background Tasks

Computing with tasks

Variable Type Constructor

Computation Expressions and the M word

Rendezvous

A rendezvous is a Future Event

Waiting for Events

Channels of Communication

Computing Primes With Tasks

Filtering for Primes

A Stream of Naturals

Sieving for Primes

Philosophers Have to Eat

Using Channels and Rendezvous to Implement

A Meeting of Philosophers

Asynchronous Communication

A Message Queue

Comment

Application = Policy + Mechanism

How to Design a Domain Specific Language

Resource Definition Framework

There is Methodology in my Ontology

Nouns and Verbs

Designing Syntax

Triple Notation

Design is Iteration

Operator Precedence Grammar

Mixing Operators

Embedding Graphs

Validation

Escaping our DSL

Variations on a Theme

Validating Triple Conditions

Translating Graphs

Representing Triple Graphs

Macro Rules

Meta Language

Meta Variables

Code Macros

After the Translation

Is There a Downside to DSLs?

Chattering Agents

A Taxonomy of Agents

Speech Actions

Programming Speech

Queries

Free Variables in Speech

Notifications

No Time

Requests

A Missing Performative

Actors

Performance Characteristics of Actors

Concurrent Actors

Boxes and Arrows

Ports and Speech

A Component in Star

Re-purposing Components

Wiring up Boxes and Arrows

There is more to a platform than this

Are We Done Yet?

Notes

Why Be a Star Programmer?

This book is about a new programming language called Star. Why, you may ask, do you need to learn yet another language? We hope to answer that question and more in the course of this book. We also aim to show you how to program effectively in Star to solve real world problems.

Programming has Changed

Real-time is normal time

Many kinds of business are becoming more and more ‘real-time’: a 100 millisecond slowdown in loading a web page can mean the loss of 5% of revenue for an e-commerce site; an unrented car, like an unrented hotel room, represents a permanent loss of business and a competitive disadvantage.

For the modern programmer, this means that applications must be engineered from the start to be responsive and multitasking – aspects that challenge even the most professional of programmers.

Programming Safely and Effectively

At the same time, safety and security are also critical: no-one likes to have their private information exposed to the bad guys. Most main-stream programming languages were designed in an era when safety was not uppermost in programmers’ minds – usually it was performance. Some seemingly trivial design choices – such as C’s conventions for laying out strings in memory – turn out to have potentially devastating security implications.

In addition, systems that are built assuming a shielded execution environment, behind closed doors as it were, are often actually expected to perform in the full glare of the Internet. Hardening programs so that they stand up to that glare can often dramatically add to the cost of development – both in time and in money.

This Train is Leaving the Station

Perhaps most importantly, we need to be able to do these things now – time to market is a critical factor in many if not most modern applications. Its no good developing the world’s best widget if you run out of ‘runway’ trying to build it.

A major bottleneck is the relative poor productivity of most modern programming languages. It is simply too hard to produce correct robust code in languages like C/C++, Python etc.

Productivity is an issue for individual programmers but is especially salient for programmer teams.

Every successful software project involves a team.

The requirements for team-based development tend to put certain aspects of programming language design into sharp focus. For example, strong types and clear interfaces may be excellent aids for individual programmers but they are absolutely paramount for team development.

More generally, in a competitive environment, the only way to reliably out-perform the competition in reaching the market is to use radically more productive technology.

Is Star for you?

Choosing a programming language – when you actually have a choice – is highly personal. Here are some reasons to think about Star.

If You Are Already a Functional Programmer

You have many choices for functional programming languages that are excellent. The author considers two languages that are principal sources of inspiration for many of the functional features of Star: Haskell and Standard ML – both of which are excellent; but not perfect.

For the functional programmer, the principal benefits of Star are readability, modernity and predictability.

One of the major drivers of the design of Haskell and (to a lesser extent) ML is conciseness. However, conciseness is not the same as readability. In modern software development environments there are many stakeholders beyond the developer. Having a language that is easy to follow by non-technical readers is a major benefit in mixed skill teams.

Like Haskell, Star has a powerful type system. Star’s type system has many features in common with Haskell’s type system – features that typically go beyond the capabilities of many OO languages. In particular, Star’s contract system is reminiscent of Haskell’s type classes; and Star’s existential and higher-kinded types give considerable expressive power to the programmer.

Star does not follow all of Haskell’s type features; and some type concepts are rephrased into terminology that is more familiar to OO programmers.

Like ML, Star has a powerful module system. However, unlike ML’s functors, Star modules are first class values. This means that there is no artificial separation between ‘ordinary’ programs and ‘functor’ programs.

The result is a balanced set of type features that provides capabilities that scale well from small programs to large systems.

Star’s evaluation is, like that of ML but unlike Haskell, strict. We believe that that makes it significantly easier to reason about the actual behavior and performance of programs. However, Star has a rich set of features that support productive concurrent and parallel programming – based on a combination of system threads and the features of Concurrent ML.

Like ML, Star is not a strictly ‘pure’ language. This was neither an accident nor an afterthought. Computer systems are built to fulfill purposeful activity (although there may be many times when the actual purpose is hard to discern). For example, if I deposit a check into my bank account, I require that the bank’s state is updated to reflect my new balance: the world has changed as a result of my action.

However, the converse does not follow: just because the world is stateful does not mean that all our programs should be needlessly stateful. Much, if not most, of a given application program can and should be crafted in a mathematical style – the merits of functional programming are very great.

Overall, the primary rationale in the design of Star is to empower the programmer in making obviously correct programs.

If You Are Already a Java (or C#, or C++) Programmer

Most OO languages are embracing some of the simpler features of functional languages. Even Java 8 with its lambda expressions and stream features represents a nod to the power of functional programming.

However, at the same time, there is a substantial gap in the capabilities of most OO languages compared to modern functional programming languages. This is a problem because the better a language is able to ‘understand’ your objectives, the better the tools will be able to support those objectives.

Fundamentally, OO languages revolve around nouns rather than verbs. Verbs (methods) are relegated to being inside the scope of some noun (object): they are not first class. However, this leads to unnatural representations where functions do not naturally fit inside some class. In functional programming languages, like Star, there is more of an balance between nouns and verbs.

Functional languages allow a more subtle interplay possible between data and functions. It is possible to have functions that are about data; it is also quite straightforward to have data structures with functions embedded in them. In fact, a simple definition of a module is a record that contains functions in it.

While OO languages like Java provide excellent data abstraction tools, there are much less effective for control abstractions. The result is that OO languages are ‘stuck in the 1970s’ when it comes to control abstractions. However, concepts such as map/reduce, computation expressions, and continuations bring a rich suite of new control possibilities that solve important problems in modern programming.

Similarly, the type systems of languages like Java (or C# or C/C++) make are not as expressive or sensitive as modern type systems in functional languages can be. Professional programmers will recognize the typical response to insufficiently expressive types: lots of casting and dynamic meta-programming. But, while powerful, these techniques amount to giving up on types and their important advantages. Furthermore, contrary to many programmers’ expectations, a modern type system is quite capable of dealing with scenarios that require dynamic programming in languages like Java.

In addition, Star’s extensibility directly addresses a real world requirement: that of supporting a separation of policy from mechanism. Typically OO languages are excellent at describing mechanisms but do not fare so well in describing policies – which are typically declarative in nature. Hence the tendency in software engineering circles to adopt text frameworks such as XML and JSON to express policies. However, these technologies lose one of the major advantages of Java – that of type safety.

Technology

The technology platform that programs are written for is also changing. Just a few decades ago most computers were single-core; nowadays most computers are multi-core and are capable of significant parallelism.

Especially spectacular is the parallelism available in modern GPUs; where a high end graphics processor may have thousands of cores capable of processing instructions in parallel. We expect that the days of personal computers with thousands of cores is not too far in the future.

Programming parallel machines with conventional languages is an exercise in frustration. This is because programming models that worked in single core computers do not scale well to highly parallel machines. One of the primary reasons for this is that state – as represented by the changing values of variables – is implicit in procedural and object oriented languages. The implicitness of state is important because it makes many programs easier to express. On the other hand, that implicitness becomes a liability in multi-threaded and parallel situations where state is no longer so well behaved.

However, Star has adopted some of the recent innovations in that make dealing with multi-tasking and parallel execution easier. These innovations layer on top of basic features such as threading and provide simpler models of execution than ‘conventional’ threaded models. Star’s computation expressions combine the best of fork-join queues and map-reduce frameworks whilst enabling a more normal style of programming.

Design Goals for Star

Star is a multi-paradigm high-level symbolic language. It is designed to be readable, accurate, high performing and extensible.

The syntax of Star is oriented towards readability rather than strict conciseness. The reason for this is that the programmer is only one of the stake holders in a given program. A readable program is one that is more easily trusted by non-programmers.

Experience also suggests that readability enhances programmer productivity also: much of team-based development involves comprehending and modifying other programmers’ code.

Star is a strongly, statically typed language. The purpose of a strong type system is to facilitate the communication of intent of the programmer. The purpose of static typing is to ensure that the compiler can rapidly ‘fail’ incorrect programs without requiring the program to be run. Furthermore, static type checking minimizes any run-time penalty for imposing type constraints.

Although Star is strongly typed, it uses type inference to eliminate most of the clutter that some type systems impose on the programmer – which itself is a productivity sink of course.

Generally, the stronger the type system, the more the language system can detect errors before programs are run. In parallel, the more expressive the type system is, the less the temptation to try to subvert or bypass the type system.

Star has a range of features that make exploiting parallelism easier to manage. For example, it has support for computation expressions and actors. Partitioning an application into different agents allows programming to follow a more human approach. Computation expressions allow the programmer to manipulate computations as easily as they do data values; that in turns greatly eases the development of parallel and concurrent applications.

There is no one technology that can solve all problems. This is as true for programming as for other domains. Star supports a range of programming paradigms that allows the developer to ‘use the best tool for the job’. However, we go beyond this ‘swiss army knife’ stance and make it straightforward to extend the language.

Virtually every non-trivial program can be factored into a combination of general purpose mechanism and specific policy for applying the mechanism. Star has powerful self-extension features that allow programmers to design their own policy structures (a.k.a. domain specific languages).

Many of Star’s own features – such as its query notation and its actor notation – are built using these extension mechanisms.

About this book

This book acts as an introduction to the language and to its use. The basic features of the language are introduced; however, this is not a reference manual: it is not intended to be a complete description of the language.

Introducing a programming language like Star can be a challenge in presentation. This is because there is a significant amount of mutual support between elements of the language.

Our strategy is to take a layered approach – we start with simple examples, occasionally skipping over certain aspects of the language without explanation. Later chapters focus on deeper, more complex topics.

For the most part, examples in the text of the book are executable. You are encouraged to try to get them running on your own system.

Getting hold of Star

The easiest way to access the compiler is to pick up the released code from Github. You can also pick up the source of the compiler from here.

The main files in the Star system are:

star100.jar This is a Java jar file that contains everything needed to compile and run Star programs. You will need an installed copy of Java 8 in order to run the compiler.

The star shell script is a convenient entry point to using the Star compiler. You may need to edit this; it assumes that the jar file is located at ~/bin/star100.jar.

The reference.pdf file is the official language definition.

Assuming that you have downloaded the release files, assuming that you have your star files in the current directory, you can compile and run a Star program using:

$ star fact.star 10

This will compile the file fact.star and run it, passing the integer 10 to the embedded program.

The first time you run the compiler it will be a little slow. This is because it also compiles the standard library into the sub-directory ./starcode/. Subsequently, the compiler will be significantly quicker.

The Star compiler generates Java byte code, which means that it relies on the JVM platform for its execution. It also means that integrating Star code with Java code is straightforward. For details of how this works we recommend the Star Language definition.

Typographical Conventions

Any text on a programming language often has a significant number of examples of programs and program fragments. We show these using a typewriter-like font, often broken out in a display form:

P has type integer;

...

We use the ... ellipsis to explicitly indicate a fragment of a program that may not be syntactically correct as it stands.

As we noted above, Star is a rich language with many features. As a result, some parts of the text may require more careful reading, or represent comments about potential implications of the main text. These notes are highlighted the way this note is.