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 ofid
field ina
a b ->id
(set): modifya
by setting itsid
field tob
a f <-id
(update): modifya
by applyingf
to itsid
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-union
s and list
s.
Some unicode characters get replaced with ascii approximations during preprocessing:
λ
becomes\
≡
becomes==
→
becomes->
←
becomes<-
≠
becomes/=
≤
becomes=<
≥
becomes>=
- Greek letters become their names (
α
becomesalpha
,Γ
becomesGamma
, 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.