Nomad

From Esolang
Jump to navigation Jump to search
Nomad
Paradigm(s) functional, probabilistic
Designed by Async Engineering
Appeared in 2018
Type system static, structural, nominal, lattice
Memory system stack-based
Computational class Turing complete
Reference implementation nomad
Influenced by Standard ML, OCaml, Elm, TypeScript, Idris 2
File extension(s) .nomad, .nmd,

Nomad is a multi-paradigm language created from 2018 to 2021 with the goal of simplifying modern programming to as few concepts as possible, in order to facilitate complexity in other areas; Specifically, probabilistic programming.


Language overview

Nomad is designed to be a simple language. There are three primary concepts at the root of the language. These concepts are recursion, pattern matching, and algebraic data types.

History

Nomad was originally created in 2018 as an experiment in lattice based type systems and type-safe uncertainty through probability monads.

Etymology

Nomad was chosen to symbolise the portability of the language, principally the type system, which aims to provide type unification between many external type systems such as JSON, Protobuf, gRPC, and SQL. Nomad is also an anagram for Monad which is primary structure in functional programming.

Type System

Nomad has a structural type system that is based on a lattice. Types can be automatically generalized or specialized by moving up or down in the lattice.

Types-hasse.png

Records are models as lattices as well. Accessing a field projects the element from the lattice. Records are extensible.

Records-hasse.png

Records and types must be inflationary to be compatible. Records which share fields with the same name but different types can be generalized to accept either type through unions.

Record-union-hasse.png

The most simple model for implementing a type system employs sets as types. All types can be considered to be sets of values. A lattice is a set with a preorder imposed on it. In Nomad, types are arranged into a lattice with a partial order. This order can be used to generalize or specialize a type. The language encodes a set of laws which govern this traversal.

Records

Records group related data together.

Point: type = {x: Int, y:Int}
point: Point = {x: 0, y: 1}

Algebraic Data Types

Data and types can be joined together.

Point2D: type = {x: Int, y: Int} 
Point3D: type = Point2D & {z: Int}

Points: type = Point2D | Point3D

In some cases, structural typing can be error prone. For example, if you have a type union specifying cardinal directions and another type union specifying suites of cards, these types will be compatible.

 Direction: type = North | East | South | West
 Suite: type = Diamond | Spade | Club | Heart

These types will compile to the same type, which may be confusing to developers. To use types nominally, you can proceed the type with an octothorp.

  Direction: type = North | East | South | West
  Suite: type = Diamond | Spade | Club | Heart
 
  directionHeading: (direction: #Direction) -> Nat 
  directionHeading= direction ? 
                              | North => 0
                              | East  => 90
                              | South => 180
                              | West  => 270

Features

Pattern Matching

Pattern matching is a core concept in Nomad. Therefore, the syntax is super lightweight. subject ? pattern1 | pattern2 Pattern matching is equivalent to match CONDITION with in ML style languages, and is similar to a switch statement in C style languages.

The match expression can branch on abstract data types:

Bool: type = False | True

toString: Bool -> String 
toString= bool ?
               | False => "false"
               | True => "true"
        

You can also use the match expression to capture variables, and can match types:


toString: a -> String
toString= a ? 
            | num: Int => f"{num}:Int"
            | bool: Bool => f"{bool ? False => "false" | True => "true"}:Bool"

Recursion

Factorial implementation with recursion and pattern matching.

factorial: Int -> Int
factorial= n ?
             | (<= 1) => 1
             | _      => n * factorial (n - 1)

Sum items in a list.

sum: (numbers :List[Int]) -> Int = 
     numbers ?
             | [] => 0
             | head :: tail => head + sum tail

Pipelines

numbers 
  |> map *2
  |> string 

Examples

Hello World

main = writeLine "hello, world"

Cards

Card:  type = { rank: Rank, suite: Suite }
// Card: type = Rank & Suite

Suite: type = Clubs | Hearts | Diamonds | Spades

Rank:  type = Two | Three | Four  | Five 
            | Six | Seven | Eight | Nine  
            | Ten | Jack  | Queen | King
            | Ace

Name: String 
Hand: List[Card]

Player: type = Name & Hand

Deck: List[Card]
Stack: List[Card]

Game= { players: List[Player] } & Deck & Stack
nextPlayer = cycle iterate Game.players

Tic Tac Toe

Mark: type = "O" | "X"
Cell: type = Option Mark

Board: [9]Cell = 
               { None, None, None
               , None, None, None
               , None, None, None
               }

viewBoard: Board -> String 
viewBoard = board => zipWithIndex map \ c: Cell & Index => max c.Index c.Mark 

The Math

Grammar

 <privateLabel> ::= [a-z][a-zA-Z0-9]+
 <exportedLabel> ::= [A-Z][a-zA-Z0-9]+
 <Label> ::= <privateLabel> | <exportedLabel>
 <Type> ::= <Expr>
 <Definition> ::= <Label> [[:<Type>] | [=<Expr>] | [:<type>=<Expr>]]

 matchExpr ::= <Expr> ? [|]? [patternExpr]+
 patternExpr ::= [|] <Expr> => <Expr>

Proofs