-
Notifications
You must be signed in to change notification settings - Fork 4
language
David Pollak
February 22, 2012
© 2011-2012 David Pollak, All Rights Reserved. Licensed under MPL 1.1
This document describes the Visi language. Visi is an open source language that blends concepts from spreadsheets, scripting languages, functional languages such as Haskell and OCaml, and other systems. The goal of Visi is to be accessible for Excel power users, yet be “correct” such that runnable code should be substantially bug-free. Visi forms the basis for the Visi.Pro platform that allows programming on iPads and those programs can run on iPads, iPhones, as well as in the cloud.
Features of Visi include:
- Guaranteed serializability of user-created data structures (like Erlang) such that data structures can seamlessly migrate across address spaces.
- Visually pleasing syntax that makes simple programs as well as very complex programs easy to understand. The syntax is whitespace-oriented and eschews curly-braces, line ending markers, etc.
- Persistent (immutable) data structures except for certain data structures that do not escape the boundaries of library calls (everything that “end users” see is immutable).
- Clear demarcations of side effects (sources [input]/sinks [output] and references) such that the order and locus of computations is invisible to the programmer until a commit operation to a sink or reference occurs.
- A type system that is simultaneously powerful and invisible. End users cannot write type annotations. Library authors can construct very complex type expressions that are evaluated at compile time to insure code correctness. Programs will not be allowed to run unless they pass the type checker. Note that getting error messages “right” will be a serious challenge for Visi.
- Visi will be self-hosted with a built-in IDE like Smalltalk. The initial IDE will be Mac OS X based.
- Visi will support incremental development such that changes can be made to “running” programs like changes can be made to a spreadsheet and the changes are immediately reflected. However, Visi programs will be compiled to various more efficient representations including converting Visi lambda calculus representations to GHC intermediate representations such that Visi programs can be compiled to any supported GHC back-ends including LLVM, native code, and potentially JavaScript. Visi can also be run interpreted on iOS devices.
- Visi, like spreadsheets, performs computations when external state changes and updates outputs. This makes Visi ideal for writing systems that rely on external data feeds and Visi can trigger events when new data from data feeds is received.
This document is an evolving description of the Visi language as well as a discussion/justification for the design decisions.
Do we need yet another computer language? Is there currently a “Cambrian explosion” of computer languages and why Visi?
Well, yes. Most computer languages, especially the ones that are cropping up these days, seem to re-visit ideas of past computer languages. They make minor syntactic changes or in other ways make small alterations to the kind of basic concepts that have been around computing for years.
There are notable exceptions. Clojure embraced Lisp syntax, but fundamentally changes mutable state into an issue of time. Scala made material advances in computer languages by blending a rich mostly consistent type system with object oriented programming. Most other languages that have been introduced this millennium are minor variants on Smalltalk or C++ or Java.
Visi takes a different approach. Visi approaches the problem of describing how a computer should respond to input in a similar manner to spreadsheets. Visi approaches computing from the perspective of a dependency graph when outputs change as inputs change and only outputs that depend on a particular input are recomputed when a particular input changes. The dependency graph is intuitive to anyone who has ever put together an Excel spreadsheet (or a 1-2-3 spreadsheet or even a VisiCalc spreadsheet.)
More broadly, my motivation for Visi is to create a language that fundamentally changes the way people program computers such that Visi is a language oriented to humans rather than a veneer on top of computing machinery. Visi is not a tool for writing compilers (although it will be mostly self-hosting). But, instead, Visi is a tool for normal people to model, to describe relationships such that a network of computers can perform calculations based on external input and generate predictable, correct output. My motivation for Visi is to change the landscape of computer languages the way that VisiCalc changed the language and computing landscape in 1979.
Let's take a look at some Visi language samples.
First, “Hello, World!”:
"Greeting" = "Hello, World!"
The lefthand side of the equation has quotes around it, meaning that it's a “Sink”. A Sink is output that can be wired up to a user interface or some other external output.
Next, let's take a number from a “Source” (an input), add 1 to the number and send it to a “Sink” called “Plus One”:
?number
"Plus One" = number + 1
It's easy to define functions:
addOne n = n + 1 // a function that adds 1 to the input
?number
"Plus One" = addOne number
And functions can be recursive:
fact n = if n == 0 then 1 else n * fact n - 1
res = fact 10 // 3628800
Syntactically, variables (and local functions) need only be offset by spaces from the upper level declaration:
f n = // add 33 to the input
v = 33 // the variable v is set to 33
n + v // return the result because it's the last line of the function
In action:
f n =
v = 33
n + v
res = f 3 // res == 36
Functions can be local as well:
f n = // calculate the factorial of the input
fact n = if n == 0 then 1 else n * fact(n - 1)
fact n
Inner functions can shadow outer function. The function in the nearest scope, wins. Also partially applied functions can be passed as parameters:
fact n = n & "hello" /* proper scoping: fact is not the inner fact */
f n = /* Test partially applied functions */
// a local fact function that is visible within this function only
fact n = if n == 0 then 1 else n * fact(n - 1)
app n fact // apply the fact function to the input
/* Apply the function f to the value */
app v f = f v
res = f 8 // 40320.0
Partially applied functions close over local scope:
f b = /* test that the function closes over local scope */
timesb n m = n * b * m
timesb /* partially apply the function which closes over
the scope of the 'b' parameter */
app v f = f v
q = f 8 // return a partially applied function
z = f 10 // return another partially applied function
res = (app 9 (app 8 q)) - ((z 8 9) + (z 1 1)) // -154
Rolling input, functions and output together:
/* Input */
?taxRate // source the tax rate
?taxable
?nonTaxable
/* Computations */
total = subtotal + tax
tax = taxable * taxRate
subtotal = taxable + nonTaxable
/* Output */
"Total" = total // sink the total
"Tax" = tax // sink the tax
And the type checker insures you don't mix types:
f = 3
d = f & "hi" // fails... can't mix a number with a String
The typer supports the identity function and type variables:
q n = n
f n = if true then n else (q n) // both q and f are generic function
Generic functions, even at multiple levels of recursion can be correctly typed:
a n = b n
b n = c n
c n = a n // a, b, and c are all generic functions
Functions can be mutually recursive without any hints to the type checker (like OCaml's let rec):
isOdd n = if n == 1 then true else not (isEven (n - 1))
isEven n = if n == 0 then true else not (isOdd (n - 1))
// define the not function
not n = if n then false else true
// the result is true (9 is odd)
res = isOdd 9
More language samples as Visi evolves.
Visi is a literate language. That means that Visi models are Markdown documentation that contain the model inside the text. This is because Visi models tell a story and the descriptive part of the story is more important than the instructions to the computer. For example:
This is a *Visi* model. This text tells the story of the model.
Add one to parameter:
```
addOne n = n + 1 // this is the logic in the model
```
I'm telling more of a story… and you can learn more about the
[Visi language](https://github.com/visi-lang/visi/wiki/language).
If the Visi parser detects two or more sets of triple back-ticks in the document, it parses only the contents of the triple back-ticks. In this way, Visi models also display correctly as Github Flavored Markdown.
The rest of this chapter will be examples of the Visi language models and will not discuss Markdown.
All expressions and functions in Visi are lazily evaluated (except that certain built in functions may be strictly evaluated to improve performance). Expressions in a model are evaluated on demand. The demand comes from a source (input) changing and recomputing all sinks (outputs) depend on that source. The Visi runtime makes no guarantee about the order of evaluation or even the location of evaluation. Visi models, like Excel models,
myFunc = 33
oneParam n = n + 1
zeroOrMore n = if n > 0 then n else 0
myFunc n = n + 1
callFunc n = myFunc n
res = callFunc 5 // res == 6
A function can be partially applied:
mult a b = a * b
times8 = mult 8
res = times8 2 // res == 16
As can an operator:
plus1 = (1 +)
res = plus1 5 // res == 6
plus = (+)
res = plus 1 2 // res == 3
Local functions can take zero or more parameters and close over local scope. For example:
// create a partially applied function that multiplies by the param
multBy param =
times a b = a * b
toReturn = times param // partially apply the local times function
toReturn
Both times and toReturn are functions local to the multBy scope. toReturn closes over local scope (the param parameter)
Visi does not have a line ending character, but leading whitespace is significant.
A line that is indented deeper than the line above it is a logical continuation of the line above. The simplest example is:
myFunc n =
n + 1
Or:
myFunc n =
if n > 0 then n
else n * -1
Local functions are nested via whitespace:
myFunc a b =
aTimes2 = a * 2
mySillyFunc n =
myInnerFunc b = b + 1 // b is scoped to the param of myInnerFunc
thing = n * 3
myInnerFunc thing // the results of mySillyFunc
(mySillyFunc b) + aTimes2 // (b * 3) + 1 + (a * 2)
At this point, there is no support for tabs, so whitespace means space characters (ASCII 32).
Visi processes information that comes from a source or input. A source can come from user input, an external process, or even from the sink (output) of another Visi model.
a source is defined by placing a ? before an identifier:
?number // a source
nextNumber = number + 1 // a function that references the number source
A sink is the result of applying a model to the value
of sources.
A sink is defined by a quoted identifier on the left hand side of an equation:
"greeting" = "Hello, World!"
Sinks can depend on sources and when a predicate source changes, all dependent sinks are computed and triggered. Trigger causes any external systems associated with the sink to be updated.
?number
"next" = number + 1
Visi has the following data types built in:
- Boolean
- Integer (8 bit, 16 bit, 32 bit, 64 bit and arbitrary precision)
- Double Precision Floating point (single precision floating point?)
- Rational numbers (numbers with arbitrary precision Integer as numerator and denominator)
- String (Unicode capable, UTF-8 encodable)
- Date with millisecond precision and TimeSpan
- Geospatial (long/lat)
- Media (image, sound, mpeg -- Yeah, they could be compound data structures, but I think it's optimal to have the data structure be native so we can lazily load the media or stream it)
- Array
- Byte Array (separate from Array for performance reasons)
Additionally, the Visi language has built-in syntax support for Lists, although List is implemented as a library. The syntax is Haskell-like:
myAnimals = ["Archer", "Madeline", "Elwood"]
ageRange = [1 .. 50]
inifiniteRange = [ 1 .. ]
head a:rest = a
tail a:rest = rest |
_ = Nil
Visi also supports tuples (Product types) at the parser level but the implementation of tuples will be done in libraries:
me = ("David", 48)
returnValue = (200, True, "stuff")
Visi has data structures that are, in ML parlance, union types.
Constants:
struct Bool2 = True | False
Simple data structures:
struct Dog(String)
Simple data structures with named properties:
struct Cat(name: String)
Union types:
struct Thing = This(String) |
That(when: Date)
Union types with common constructors:
struct Person(String, age: Int) =
Kid() |
Parent(kids: [Person])
daniel = Kid("Daniel", 8)
david = Parent("David", 48, [daniel])
Union type with properties:
struct WritingInstrument =
property
size = Millimeter 7
Pencil(color: String) |
Pen(inkColor: String)
// Both Pen and Pencil have a size property
struct Animal =
Moose(height: Int)
property
hasHorns = True
Fish(freshWater: Bool)
// Only Moose has the hasHorns property
All union types are also product types (tuples) where the arity of the tuple is the number of Type Constructor parameters. So the following is a struct definition that also defined a 2 position tuple:
struct Album(name: String, length: TimeSpan)
Type Constructor/Extractor:
dogsName Dog(name) = name
kidsName Kid(name, _) = name
Nominal pattern matching (will match any type with a name property):
name (name => theName) = theName // you can pass Cat or Person to the name function
names (name => ) = name // shorthand to set the local name variable
Positional pattern matching (match any tuple with the same arity):
first (ret, _) = ret
second (_, ret) = ret
Positional pattern matching with specific types:
firstString (str: String, _) = str
Nominal pattern matching with testing. The example
below will match any type that has a name property that is equal
to "fred" and has an age property that's an Int. The return type
is Box Int (Box is similar to Option or Maybe) because the
pattern is non-exhaustive.
fredsAge (name == "fred", age: Int =>) = age
Pattern matching against a type constructor:
fredsAge2 Person(name == "fred", age =>) = age // Box Int
Visi is structurally typed, like OCaml. This means that any type with a given property or method can be a parameter to a function or method that accesses the property/method. Find the age of any type with an age property/method:
anyAge n = n.age // polymorphic in the return type of age
Property/method accessors can also be curried so that you don't need the thing that the accessor is applied to:
anyAge2 = #age
anyAgeTest n =
n.age == #age n
We can define methods on a type:
struct Foo(age: Int)
methods
old? = self.age > 85
addToAge n = self.age + n
We can also define properties on a type:
struct Bar(age: Int)
property
name = "Bar"
All structs are immutable. So, to create new instances, we use updators (Visi may implement lenses, but not right now… also maybe zippers in the future).
kid = Kid "Daniel" 7
birthday = kid.= 8
birthday == Kid "Daniel" 8
And the updator can be partially applied:
make8 = #=age 8
birthday == make8 kid
We can also update via a function:
nextYear k = k.> (+ 1)
nextYear2 = #>age (+ 1)
birthday == nextYear kid
birthday == nextYear2 kid