OM

From Esolang
Jump to navigation Jump to search

OM stands for "Only Macros". Everything that happens in OM happens because of a macro being evaluated. Because of this, there is no distinction between code and data in OM. OM was inspired by LISP and Wolfram and is similar to ///.

Language overview

An OM program is just an OM expression. Macros are evaluated on it until no macros match anything in it. The result is returned as output.

Expressions

Textually, an expression on OM is any string with proper bracket matching. A bracket can be escaped with ` to make it not count as a bracket. The following are valid expressions:

abd (cool stuff [ {}{}{(((`]`]`]`]`}`}`)`))))}])
expr
()

The following are not:

(
[]]
(`)
([)]

Internally, an OM expression is represented as a list of nodes. Each node has a string value, a type, and a list of child nodes. There are six types:

Type Text Representation Function
PAREN ( ) Puts the nodes inside it into a PAREN node without evaluating macros on them.
SQUARE [ ] Macros are evaluated on nodes in a SQUARE node before nodes outside of brackets. Evaluates to a list of nodes not in a PAREN node.
CURLY { } Puts the nodes inside it into a PAREN node after evaluating macros on them.
CAPTURE ~token A CAPTURE node with the token as the value. Plays an important role in macros.
Normal token A NORMAL node with the token as the value. Many uses.

Macros

A macro is defined like this:

form -> product-form

The form and the product form will both be individual nodes. If the form or the product-form are a PAREN node, their children will be the form or product-form. This macro will replace any expression (not in a PAREN node) matching the form and replace it with a corresponding expression matching the product-form. For example,

(a b a) -> (b a b)

will replace any instance of a NORMAL node with value "a" followed by one with "b" with one with "b" and one with "a", so

a b a c a d a

becomes

b a b c a d a

Notice that (a b a) does not match any three nodes where the first and last are the same. (a b a) refers to specifically a node with value "a", one with "b", etc.

Suppose you did want to match any three nodes where the first and the last are the same. You could do that with CAPTURE nodes. It would look like this:

(~a ~b ~a swap-inner) -> (~b ~a ~b)

That macro would match any three nodes where the first and the last are the same. For examples,

cat dog cat swap-inner

would become

dog cat dog

Also,

moo moo moo swap-inner

would become, after the macro is applied to it,

moo moo moo

Captures with different names do not have to match different nodes, even though captures with the same name do have to match the same node.

Conditional macros are only evaluated when a certain condition holds. This condition is represented as an OM expression that should evaluate to a NORMAL node with "True" or "False." Conditional macros are defined like this:

(~a) -> (~b) if (~c)

For example,

(abs ~i) ->  (0 - ~i) if (~i < 0)
(abs ~i) ->  (~i) if (~i >= 0)

(-, < and >= are all built-in macros).

Precedence

Nodes in (square and curly) brackets are evaluated before nodes outside brackets (expressions in PARENs are not evaluated at all), and macros with longer forms are evaluated before ones with shorter forms. Newer macros are evaluated before older macros, and a longer, older macro is evaluated before a shorter, newer macro. Whenever a macro is evaluated, evaluation starts all over again from the earliest-evaluated macros. It is essential to remember all five of these rules of precedence to code in OM.

Built-in macros

There are several macros built-in to OM. They are:

Name Form Result
DEFMAC ~a -> ~b Makes a macro with ~a as the form and ~b as the product form. If ~a or ~b are a PAREN, they will be unwrapped once. Evaluates to nothing.
DEF_CONDMAC ~a -> ~b if ~c Makes a conditional macro with ~a as the form, ~b as the product form, and ~c as the condition.
LOC loc ~a ~prog Evaluates to ~prog with all nodes matching ~a being given one unique id common to all of them. This stop them from matching other nodes.
BOOL bool ~b Returns ~b cast to either a NORMAL node with a value of "True" or "False".
PR pr ~a Prints the value of ~a.
UNW unw ~a Evaluates to the children of ~a.
IND ind ~i ~l Evaluates to the ~ith element of ~l.
LEN len ~l Evaluates to the number of children in ~l.
EXPD expd ~a Evaluates to a PAREN with a NORMAL child for each character in the val of ~a.
WRAP wrap ~l Evaluates to a NORMAL node with a val equal to all the vals of the children of ~l concatenated.
INP inp Evaluates to a line of keyboard input.
CHAR char ~i ~i is an integer. Evaluates to a NORMAL node with the corresponding Unicode character for ~i as its value.
ORD ord ~c ~c is a character. Evaluates to a NORMAL node with the unicode number for ~c as its value.
+, -, *, /, %, **, >, <, >=, <= ~a op ~b Evaluates to a NORMAL node with the op applied to ~a and ~b as its value. "%" is modulo, "**" is exponentiation.

Code samples

Although there are no built-in conditionals in OM, it is easy to make one using two macros:

(cond ~a True ~b) -> (unw ~a)
(cond ~a False ~b) -> (unw ~b)

It is also possible to make a while loop:

(~a while ~b) -> (cond ([unw ~a] ~a while ~b) unw ([bool [unw ~b]]) () )

A foreach loop takes a bit more doing:

(~a FOR ~o IN ~l WITH ~i) -> ([~i -> 0] [ ( [[~o -> [ind [~i] ~l]] [unw ~a]] [~i -> [[~i] + 1]]) while ([~i] < [len [~l]])] )
(~a for ~o in ~l) -> (~a FOR ~o IN ~l WITH [loc i (i)])

The "loc i (i)" evaluates to an "i" with a unique id that is passed to the FOR macro as the index variable. It's possible to define variables of nodes:

(get ~obj ~var) -> ()
(~obj has ~var) -> (False)
(set ~obj ~var ~val) -> ( (get ~obj ~var) -> (~val) (~obj has ~var) -> (True) )
(del ~obj ~var) -> ( (get ~obj ~var) -> () (~obj has ~var) -> (False) )

The "is" example:

(~a is ~b) -> (False)
(~a is ~a) -> (True)

Computational class

OM is Turing-complete by reduction from brainfuck:

LB -> `[
RB -> `]
(match-rb ~ind ~l) -> (ind -1 {loc num (loc i (loc char ([num -> 1] [i -> [~ind]] [ ([i -> [[i] + 1]] [char -> [ind [i] ~l]] [cond (num -> [[num] + 1]) [[char] is [LB] ] () ] [cond (num -> [[num] - 1]) [[char] is [RB] ] ()]) while ([num != 0]) ] [i] ) ) ) } )
(match-lb ~ind ~l) -> (ind -1 {loc num (loc i (loc char ([num -> -1] [i -> [~ind]] [ ([i -> [[i] - 1]] [char -> [ind [i] ~l]] [cond (num -> [[num] + 1]) [[char] is [LB] ] () ] [cond (num -> [[num] - 1]) [[char] is [RB] ] ()]) while ([num != 0]) ] [i] ) ) ) } )

(WIPE-TAPE) -> ( (get tape ~a) -> (0.0))
(ENS-VAL) -> (cond () [tape has [ptr]] (set tape [ptr] 0.0))

(PTR-R) -> ([ptr -> [[ptr] + 1]] ENS-VAL)
(PTR-L) -> ([ptr -> [[ptr] - 1]] ENS-VAL)
(INC) -> (set tape [ptr] [[get tape [ptr]] + 1])
(DEC) -> (set tape [ptr] [[get tape [ptr]] - 1])
(CHR-O) -> (pr [char [get tape [ptr]]])
(CHR-I) -> (set tape [ptr] [ord [ind 0 [expd [inp]]]])
(L-LP) -> (cond (PROG-I -> [match-rb [PROG-I] [prog]]) [[get tape [ptr]] is 0.0] ())
(R-LP) -> (cond (PROG-I -> [match-lb [PROG-I] [prog]]) [not [[get tape [ptr]] is 0.0]] ())

(DO-BF (>) ) -> (PTR-R)
(DO-BF (<) ) -> (PTR-L)
(DO-BF (+) ) -> (INC)
(DO-BF (-) ) -> (DEC)
(DO-BF (.) ) -> (CHR-O)
(DO-BF (,) ) -> (CHR-I)
(DO-BF (`[) ) -> (L-LP)
(DO-BF (`]) ) -> (R-LP)

(run-bf ~prog) -> (loc c ([ptr -> 0.0] [ENS-VAL] [WIPE-TAPE] [PROG-I -> 0] [prog -> (~prog)] [ ( [c -> {{[ind [PROG-I] [prog]]}} ] [DO-BF [c]] [PROG-I -> [[PROG-I] + 1]] ) while ([PROG-I] < [len [prog]]) ] ) )
(rbf) -> (run-bf [expd [inp]])

External resources