The Orange programming language compiler.
Functional languages, especially pure functional languages like Haskell, have many powerful features that traditional imperative languages lack. Unfortunately they suffer from complexity and unfamiliarity, and often have to resort to an imperative style when dealing with side effects. To bridge this gap we created Orange, an easy to learn object-functional language that supports the best features of both object-oriented and purely-functional languages.
- Familiar syntax and semantics
- Simple and extensible classes
- Generic pattern matching
- Partial lazy evaluation with lazy parameters
- Control flow (
ifelsewhilefor) as functions - The effect monad with resumable exceptions
- Continuations with higher order resume (
resume(resume))
In the spirit of the Repl.it language jam, we'll use Orange to implement a
simple interpreter. You can try the examples by pasting them into the Orange
repl, or you can test out the end result using import "examples/Language.oj".
The repl can be started with npm install and npm start.
To begin, we'll define a simple arithmetic language.
import "std/Prelude.oj"
class IntExpr(int)
class AddExpr(lhs, rhs)
class MulExpr(lhs, rhs)
Classes in Orange are similar to data classes in other languages. They can be
constructed using their name (IntExpr(1)) and their fields can be
accessed with dot notation (expr.int). Methods can be defined on classes
outside of their definition (def IntExpr.square()) so that users can extend
existing classes with new methods.
Now that we've declared our data structure, we can implement an interpreter with pattern matching and recursion.
def Any.eval() match (this) {
IntExpr(int) int
AddExpr(lhs, rhs) lhs.eval() + rhs.eval()
MulExpr(lhs, rhs) lhs.eval() * rhs.eval()
}
// 2
AddExpr(IntExpr(1), IntExpr(1)).eval()
The match keyword is similar to pattern matching in functional languages or
switch statements in imperative languages. It allows us to branch on the type
of an expression and deconstruct it, which we can then use to evaluate the
expression.
We declare eval as a method on Any. The Any type is the top type (Object)
for Orange, which allows eval to work for any object that has matchIntExpr,
matchAddExpr, or matchMulExpr defined.
This arithmetic language is neat, but it only interprets simple programs. To add functions and application, we'll need an environment.
import "std/Control.oj"
class Env(get)
def emptyEnv
Env((name) do "undefined " + name)
def Env.insert(name, value)
Env((n) if (n == name) { value }.else { this.get(n) })
Here we define an environment as a function from a name to a value. The empty
environment is a function which always throws an exception (do in Orange is
similar to throw, but more powerful). Inserting a value into an environment
creates a function that returns that value if the name is equal.
The line import "std/Control.oj" imports the if function, which uses
trailing block expressions to provide a convenient if expression. Since if is
just a function, we could have equivalently written
if(n == name, value).else(this.get(n)). Behind the scenes, if uses lazy
parameters to prevent evaluation of unused branches
With our environment implemented, we can now interpret functions and application.
class IdentExpr(name)
class LambdaExpr(name, expr)
class ApplyExpr(fn, arg)
def Any.eval(env) match (this) {
IntExpr(int) int
AddExpr(lhs, rhs) lhs.eval(env) + rhs.eval(env)
MulExpr(lhs, rhs) lhs.eval(env) * rhs.eval(env)
IdentExpr(name) env.get(name)
LambdaExpr(name, expr) (arg) expr.eval(env.insert(name, arg))
ApplyExpr(fn, arg) fn.eval(env)(arg.eval(env))
}
def Any.evalRoot() this.eval(emptyEnv)
// 2
LambdaExpr("a", IdentExpr("a")).evalRoot()(2)
// 4
LambdaExpr("a", MulExpr(IntExpr(2), IdentExpr("a"))).evalRoot()(2)
// 4
ApplyExpr(LambdaExpr("a", MulExpr(IntExpr(2), IdentExpr("a"))), IntExpr(2)).evalRoot()
This evaluator leverages Orange's functions and closures to avoid writing variable substitution or closure capturing code. As a bonus we get full compatability with Orange, allowing us to use functions in our mini language as though they were Orange functions.
With our evaluator complete, we can move on to the parser. We'll need to define a reader effect to read from a string, but first we'll define a simpler effect to introduce the concept.
class Get()
class Set(state)
def get() do Get()
def set(state) do Set(state)
def modify(f) set(f(get()))
The state effect represents a changing state, where get returns the current
state and set changes the state. We also define modify, which applies a
function to the current state. Right now these functions will simply terminate
the program. To make them work properly, we'll need to define a handler
(handle in Orange is similar to catch, but more powerful). Since this is a
rather complicated function, we'll build it step by step.
def mutable(state, lazy f)
handle (f()) (effect) match (effect) {
Get() resume(state)
Set(newState) resume({})
}
// 3
mutable (2) { get() + 1 }
mutable is a function that takes in a state and a lazy expression to evaluate
with that state. Lazy expressions are simply expressions that are passed as zero
argument functions. handle evaluates the expression and catches any effects
thrown. If the effect is Get, it resumes evaluation with the state. If the
effect is Set, it resumes evaluation with the empty block.
At the moment, this function isn't doing much mutating. It also cannot handle more than one effect, as effects in the resume function are not being handled. We can solve both of these using recursion.
def mutable(state, lazy f)
handle (f()) (effect) match (effect) {
Get() mutable(state) { resume(state) }
Set(newState) mutable(newState) { resume({}) }
}
// 3
mutable (0) {
set(1)
modify((x) x + 2)
get()
}
By resuming in our handler, we can handle any number of effects. Passing the new state to our handler allows us to continue evaluation with the new state. Combining these two allows us to easily use mutable variables.
Before we can continue, there is one last change we need to make to our mutable handler. It currently handles every effect, which prevents us from composing it with other effect handlers.
def mutable(state, lazy f)
handle (f()) (effect) match (effect) {
Get() mutable(state) { resume(state) }
Set(newState) mutable(newState) { resume({}) }
Any() {
let cont do effect
mutable(state) { resume(cont) }
}
}
The Any case matches any object and immediately re-throws it. If it is
handled, it binds the result to cont and resumes evaluation. let is used
instead of def to declare local variables, but cannot define recursive
functions.
With our mutable effect finished, we can now implement the reader effect.
class Next()
class HasNext()
class Peek()
def next() do Next()
def hasNext() do HasNext()
def peek() do Peek()
def readString(string, i, lazy f)
handle (f()) (effect) match (effect) {
Next() readString(string, i + 1) { resume({}) }
HasNext() readString(string, i) { resume(i < string.length()) }
Peek() readString(string, i) { resume(string.charAt(i)) }
Any() {
let cont do effect
readString(string, i) { resume(cont) }
}
}
The reader effect supports three operations: next, which will advance the
reader one element; hasNext, which will be true if there is another element to
read; and peek, which will return the current element. The state of the reader
is stored as a string and and index, though one could write a handler which
reads from a file or a list of characters.
We can use this effect to define an integer parser.
def IntExpr.toString() this.int.toString()
def charIsInt(c)
c >= '0' && c <= '9'
def charToInt(c)
c.toInt() - '0'.toInt()
def while(lazy condition, lazy then)
if (condition()) {
then()
while (condition()) { then() }
}.else {}
def parseIntExpr()
mutable (0) {
while (hasNext() && charIsInt(peek())) {
let char peek()
next()
modify((sum) sum * 10 + charToInt(char))
}
IntExpr(get())
}
// 123
readString("123", 0, parseIntExpr())
parseIntExpr uses both mutable and read effects, creating a mutable integer
and modifying it while the next character is an integer. while is implemented
as a lazy function which recursively tests its condition. When the parser
reaches a non-integer character, it wraps the result in an integer expression
and returns it.
With the root parser done, we can use precedence climbing to parse addition and multiplication.
def AddExpr.toString() "(" + this.lhs.toString() + " + " + this.rhs.toString() + ")"
def MulExpr.toString() "(" + this.lhs.toString() + " * " + this.rhs.toString() + ")"
def ifEnd(lazy then, lazy f)
if (hasNext().not()) { then() }.else { f() }
def skipIgnored()
while (hasNext() && peek() == ' ') {
next()
}
// We'll implement this later
def parseApplyExpr parseIntExpr
def parseMulExpr() {
let expr parseApplyExpr()
skipIgnored()
ifEnd (expr) {
if (peek() == "*") {
next()
MulExpr(expr, parseMulExpr())
}.else { expr }
}
}
def parseAddExpr() {
let expr parseMulExpr()
skipIgnored()
ifEnd (expr) {
if (peek() == "+") {
next()
AddExpr(expr, parseAddExpr())
}.else { expr }
}
}
// ((2 * 2) + 1)
readString("2 * 2 + 1", 0, parseAddExpr())
// (1 + (2 * 2))
readString("1 + 2 * 2", 0, parseAddExpr())
skipIgnored skips whitespace and is called at the beginning of each parser.
ifEnd is a simple convenience function that keeps the parser from running past
the end of the string. parseAddExpr and parseMulExpr are both recursive,
parsing an expression and then optionally parsing an operator. Since
multiplication has higher precedence than addition, it is defined first.
The rest of the parser is simply an extension to the existing parser.
def IdentExpr.toString() this.name
def LambdaExpr.toString() "(λ" + this.name + " " + this.expr.toString() + ")"
def ApplyExpr.toString() "(" + this.fn.toString() + " " + this.arg.toString() + ")"
def parseParens() {
let expr parseAddExpr()
if (peek == ')') {
do "Expected ')'"
}.else {
next()
expr
}
}
def charIsIdent(c)
c >= 'a' && c <= 'z'
def parseIdentExpr()
mutable ("") {
while (hasNext() && charIsIdent(peek())) {
let char peek()
next()
modify((ident) ident + char.toString())
}
IdentExpr(get())
}
def parseLambdaExpr() {
let ident parseIdentExpr()
skipIgnored()
LambdaExpr(ident.name, parseAddExpr())
}
def parseAtomicExpr() {
skipIgnored()
ifEnd (do "Unexpected end of reader") {
if (peek() == '(') {
next()
parseParens()
}.elif (peek() == '\\') {
next()
parseLambdaExpr()
}.elif (charIsInt(peek())) {
parseIntExpr()
}.elif (charIsIdent(peek())) {
parseIdentExpr()
}.else {
do "Unexpected character '" + peek().toString() + "'"
}
}
}
def parseApplyTrail(expr) {
skipIgnored()
ifEnd (expr) {
if (peek() == ')') {
next()
expr
}.else {
parseApplyTrail(ApplyExpr(expr, parseAtomicExpr()))
}
}
}
def parseApplyExpr() {
let expr parseAtomicExpr()
skipIgnored()
ifEnd (expr) {
if (peek() == '(') {
next()
parseApplyTrail()
}.else { expr }
}
}
// (2 * (2 + 1))
readString("2 * (2 + 1)", 0, parseAddExpr())
// x
readString("x", 0, parseAddExpr())
// (λx x)
readString("\\x x", 0, parseAddExpr())
// ((x 1) 2))
readString("x(1 2)", 0, parseAddExpr())
With the parser complete, we can connect the parser and evaluator to define an eval function.
def eval(string)
readString(string, 0, parseAddExpr()).evalRoot()
// 4
eval("2*2")
def inc eval("\\x x + 1")
// 2
inc(1)
While this language is not particularly complex, it shows how Orange's small feature set (definitions, functions, classes and effects) can be used to implement non-trivial programs with familiar yet extensible semantics. Further extensions would require the backtracking and ambiguity effects which, while really cool, would take too long to properly implement, test, and explain. If you're interested though, here's a prototype.
def readString(string, i, lazy f)
handle (f()) (effect) match (effect) {
Next() readString(string, i + 1) { resume({}) }
HasNext() readString(string, i) { resume(i < string.length()) }
Peek() readString(string, i) { resume(string.charAt(i)) }
// Attempts to resume with try, handling any effects by resuming with else
Backtrack(try, else)
handle (readString(string, i) { resume(try()) }) { resume(else) }
Any() {
let cont do effect
readString(string, i) { resume(cont) }
}
}
// Handles the ambiguity effect by collecting all possible results in a list.
def ambiguousList(lazy f)
handle (singleton(f())) (effect) match (effect) {
// Concatenates the results of resuming with true and resuming with false
// Note: list concatenation isn't currently implemented
Ambiguous() ambiguousList { resume(true) } + ambiguousList { resume(false) }
Any() {
let cont do effect
writeList(list) { resume(cont) }
}
}
Since Orange was implemented in 21 days during the Repl.it language jam, there are lots of cool features that we were unable to implement. This is an incomprehensive list of features that could potentially be added to Orange in the future.
Orange's current syntax is sufficent but incomplete. Some examples of additional
syntax include infix application, unary operators, improved def and let,
handle default matching, newline statement terminators, and additional
patterns for pattern matching.
Multiple effects can be approximated with unique objects, but there is currently
no way to generalize named effects. Named effects work especially well with
infix operators, allowing traditional name = value syntax
class Write(unique, elem)
def Any.write(elem) do Write(this, elem)
infix right 1 += write
// Approximates named effects with unique objects
def Unique.writeList(list, lazy f) {
handle ({ f() list }) (effect) match (effect) {
Write(unique, elem)
if (unique == this) {
elem : writeList(list) { resume({}) }
}.else {
let cont do effect
writeList (list) { resume(cont) }
}
Any() {
let cont do effect
writeList (list) { resume(cont) }
}
}
}
Any().writeList(nil, (x) {
Any().writeList(nil, (y) {
x += 1
y += 2
})
})
Let syntax currently desugars to the following declaration.
def let(x, f) f(x)
let(2, (x) ...)
This could be extended to work with any function that takes a continuation.
def mutable(x, f) Any().mutableState(x, (var) f(var))
let mutable x 0
let mutable x 0
x += 2
++y
Lenses are necessary when dealing with immutable data to update nested fields. This can be done by generating lenses for all fields by default while allowing classes like List to define their own custom lenses.
class Address(street, city)
class Person(name, address)
def person ...
import "std/Lens.oj"
// Colon is being used for lens composition
person:address:street.get()
person:address:street.set("123rd St")
Adding a type system to Orange has its pros and cons. On the upside, it greatly improves static analysis for both objects and effects. On the downside, it reduces flexibilty and steepens the learning curve for new functional programmers. While we are generally in favor of type systems, we are not sure if it is the correct choice for Orange--and even if it were, it would take lots of time that could be going towards implementing other features.
If we were to add a type system, it would likely be an extension of Scala's Dot Calculus with effect types and bidirectional type checking. Orange's syntax for such a type system would attempt to match the familiarity the rest of the language.
Orange is written in PureScript, runs on JavaScript, and builds with npm and spago.
spago install
npm installspago build
npm run replOrange includes a simple VSCode plugin located in vscode.