Concatenative programming language.

To run:

• egi: interactive repl (= node edsger.js /path/to/lib/directory repl)
• egc <src> <dst>: compile <src> to bytecode (= node edsger.js /path/to/lib/directory compile <src> <dst>)
• egd <src>: disassemble bytecode (= node edsger.js /path/to/lib/directory disassemble <src>)
• eg <src>: run compiled bytecode (= node edsger.js /path/to/lib/directory run <src>)

# line comment

"hello, " "world" ++
# "hello, world"

Define functions with ==:

0 tri == 0
n tri == n (n 1 -) tri +

100 tri
# 5050

Define multiple cases at once by chaining equations together:

0 even? == 1 odd? == true
1 even? == 0 odd? == false
n even? == (n 1 -) odd?
n odd? == (n 1 -) even?

Quote with square brackets:

[1 +]
# [3 0 0 0 1 32]

Unquote with function application operator .:

1 [1 +] .
# 2

Define and apply an anonymous function with \ and ->:

1 2 \ a b -> b a
# 2 1

Anonymous functions can also have multiple cases:

1 \ 0 -> "zero"
       _ -> "something else"
# "something else"

Define tagged variant types with data.

e.g. a boolean data type:

data bool == true | false

After this declaration, you can pattern match on the tags true and false:

true show == "true"
false show == "false"

You can also match on all values of some type by tagging pattern variables with the type name:

a bool f == "got a bool" # only matches if a is true or false

The primitive types integer, number, string, and function have corresponding type names, so you can match on them as well:

_ integer f == "got an integer"
_ number f == "got a number"
"abc" f == "got the string `abc'"
_ string f == "got a string"
[1 +] f == "got a successor function"
_ function f == "got a function"

(Pattern matching on "quoted function literals" just compares compiled bytecode.)

Variant tags can also take arguments. Here's an option type:

data option == _ itself | nothing

You can also omit the type name (option in this case) if you don't want to be able to pattern match on it.

If the underscores in a data declaration are replaced with an identifier id, that identifier can be used like a record field. The compiler will automatically generate three helper functions:

• a id (get): extract the value of id field in a
• a b ->id (set): modify a by setting its id field to b
• a f <-id (update): modify a by applying f to its id field

For example,

data nil | tail head cons

will generate partial functions tail, ->tail, <-tail, head, ->head, and <-head that manipulate the first and second fields of a cons pair.

Pattern variables prefixed by a backtick are interpreted as as-patterns:

(a b cons) `c destruct-and-copy == a b c
nil destruct-and-copy == nil nil nil

nil 1 cons destruct-and-copy
# nil 1 (nil 1 cons)

Functions can be overloaded by defining patterns that match on different tags.

e.g. this map function works on both lists and options:

nothing f map == nothing
a itself f map == a f . itself

nil f map == nil
t h cons f map == t f map h f . cons

Internally, accessors are just autogenerated functions that perform pattern matching, so they can be overloaded as well.

e.g. with the data declarations below, head and tail work on both lists and creatures:

data nil | tail head cons
data head body tail creature

All pattern matches must be exhaustive and reachable--the compiler automatically deduces the least general possible type that covers all the given patterns in a function definition or lambda expression and checks the patterns with respect to it. This check isn't as strong as it would be in a statically typed language, but it helps keep definitions sane while still allowing functions that are difficult to assign simple types to, like f n rep (that just applies a function f to the stack n times).

e.g. the compiler infers the type "optional list whose first item (if it exists) is an integer" for the lambda expression below, and complains that other values inhabited by this type aren't handled.

bad == \ nil 3 cons itself -> 1
# Error:
#   In a definition of `bad':
#     In a lambda expression:
#       Patterns are not exhaustive:
#         (((nil) (3 int) cons) itself)
#       The following inferred cases are not satisfied:
#         nothing?
#         (nil? itself?)
#         ((nil? (integer? ≠ 3) cons?) itself?)
#         (((_? _? cons?) integer? cons?) itself?)

Conversely, the final pattern in this lambda expression is unreachable, since all integers are numbers:

bad == \ a number -> "got number"; a integer -> "got integer"
# Error:
#   In a definition of `bad':
#     In a lambda expression:
#       Pattern ('1 integer) is unreachable.
#       Previous patterns were:
#         ('1 number)

Since function overloading relies on pattern matching and the language isn't statically typed, it can be hard to define functions tacitly, resulting in a lot of repeated code. For example, the latex module overloads the arithmetic operators + - * and / in order to handle arithmetic on expr objects, which represent LaTeX expressions. These definitions just pass their inputs on to a helper function:

data _ _ expr

a b expr c d expr + == a b expr c d expr "+" 60 binop
a b expr c d expr - == a b expr c d expr "-" 60 binop
a b expr c d expr * == a b expr c d expr "\\cdot " 50 binop
a b expr c d expr = == a b expr c d expr "=" 100 binop
a b expr c d expr lt == a b expr c d expr "<" 70 binop
a b expr c d expr gt == a b expr c d expr ">" 70 binop
a b expr c d expr le == a b expr c d expr "\\le " 70 binop
a b expr c d expr ge == a b expr c d expr "\\ge " 70 binop
a b expr c d expr , == a b expr c d expr "," 70 binop

This is really repetitive, but if we tried to eta-reduce each definition, writing something like

+ == "+" 60 binop

then they would match against any input, which is too broad--any future definition of + would be considered an unreachable pattern.

A for block factors out these repetitions while leaving the function open for additional overloads:

for _ _ expr _ _ expr
  + == "+" 60 binop
  - == "-" 60 binop
  * == "\\cdot " 50 binop
  = == "=" 100 binop
  lt == "<" 70 binop
  gt == ">" 70 binop
  le == "\\le " 70 binop
  ge == "\\ge " 70 binop
  , == "," 70 binop

It desugars into normal function definitions with as-patterns:

_ _ expr `a _ _ expr `b + == a b "+" 60 binop
_ _ expr `a _ _ expr `b - == a b "-" 60 binop
_ _ expr `a _ _ expr `b * == a b "\\cdot " 50 binop
_ _ expr `a _ _ expr `b = == a b "=" 100 binop
_ _ expr `a _ _ expr `b lt == a b "<" 70 binop
_ _ expr `a _ _ expr `b gt == a b ">" 70 binop
_ _ expr `a _ _ expr `b le == a b "\\le " 70 binop
_ _ expr `a _ _ expr `b ge == a b "\\ge " 70 binop
_ _ expr `a _ _ expr `b , == a b "," 70 binop

The header of the for block can also contain multiple patterns, in which case a definition is generated for each pattern. For example, here are how number and string equality are defined in prelude:

for _ number _ number | _ string _ string
  = == cmp λ 0 -> true; _ -> false

After desugaring:

_ number `a _ number `b = == a b cmp λ 0 -> true; _ -> false
_ string `a _ string `b = == a b cmp λ 0 -> true; _ -> false

Code inside a with block will apply a given function after literals (numbers, integers, and strings) and unbound variables (which are converted into string literals).

For example, the latex module uses this to make it easier to generate LaTeX code:

import latex
#

with latex
  x 2 ^ 2 / C + x der x =
# ("\\frac{\\mathrm{d}}{\\mathrm{d}x}{\\left(\\frac{{x}^{2}}{2}+C\\right)}=x" 100 expr)

with can also be useful for building compound literals:

import prelude set
#

nil with cons 1 2 3 4 5
# (((((nil 1 cons) 2 cons) 3 cons) 4 cons) 5 cons)

leaf make-set with insert 0 -1 2 -2 3 -3 4 -4 5
# ((((((leaf -4 nothing leaf node) -3 nothing leaf node) -2 nothing leaf node) -1 nothing leaf node) 0 nothing (leaf 2 nothing (leaf 3 nothing (leaf 4 nothing (leaf 5 nothing leaf node) node) node) node) node) make-set)

The following automatically generates implementations of show, compare, =, and map for the option type:

data option == nothing | from-itself itself deriving show | compare | = | f map

Internally, the following function definitions are generated:

a option show == a ->primitive show
a option b option compare == a ->primitive b ->primitive compare
a option b option = == a ->primitive b ->primitive =
a option f function map == a ->primitive f map

->primitive partially represents any data type in terms of (string, list) pairs.

data list == nil | init last cons
data tagged-union == _ _ :

a itself ->primitive == nil a cons "itself" :
nothing ->primitive == nil "nothing" :

So to make any function f derivable, you can just implement it for tagged-unions and lists.

Some unicode characters get replaced with ascii approximations during preprocessing:

• λ becomes \
• ≡ becomes ==
• → becomes ->
• ← becomes <-
• ≠ becomes /=
• ≤ becomes =<
• ≥ becomes >=
• Greek letters become their names (α becomes alpha, Γ becomes Gamma, etc.)

A where clause defines local bindings for a function definition:

n fib == 1 1 n fib' instead where
  _ a instead == a
  a b 0 fib' == a b
  a b n fib' == (a b +) a (n 1 -) fib'

The bytecode keyword lets you write bytecode directly. For example, here are definitions of the arithmetic operators:

a number b number + == bytecode 9 2 9 1 16
a number b number * == bytecode 9 2 9 1 17
a number b number - == bytecode 9 2 9 1 18
a number b number / == bytecode 9 2 9 1 19

Edsger is whitespace-sensitive. Most of the rules are adapted from my parenthesizer, with keywords and semicolons taking the place of opening and closing parentheses.

Use node edsger.js preprocess <src> to see how semicolons are inferred from indentation.