Amycus Severus

From Esolang
Jump to: navigation, search

Amycus Severus is a Turing-equivalent functional programming language that is a restricted variant of Amycus. Amycus is an esoteric programming language that was born from a misunderstanding by b_jonas over an esoteric programming language by David Madore.

Definition

A value in Amycus Severus is either a natural number of unbounded size, or a finite size list of Amycus Severus values. Lists are written as <x1, …, xn> where n is a natural number, and x1, … xn are values. (You could think of Amycus Severus values as binary trees with a natural number in each leaf. A list can contain numbers or lists, or the two mixed. Amycus Severus cannot create circular or infinite lists.)

Amycus Severus programs are list values whose head is an opcode number. Amycus Severus takes such a program, and a single input argument which is an Amycus Severus value (number or list), and gives an Amycus Severus value as the result. Evaluation is defined by the following recursive definition, where E(p, x) = y means that the program p on the input x evaluates to the value y.

Rule 0. 
E(<0>, x) = x
Rule 1. 
E(<1, c>, x) = c
Rule 2. 
E(<2>, <x: y>) = 1 + x
Rule 3. 
E(<3, n>, <x1, …, xn>) = xn, provided 0 < n
Rule 4. 
E(<4>, <m, n, x, y>>) = (if m == n then x else y) provided m, n are both natural numbers
Rule 5. 
E(<5, q, p1, …, pn>, x) = E(q, <E(p1, x), …, E(pn, x)>)
Rule 6. 
E(<6>, <p, x>) = E(p, x)


Interpreter

The following example interpreter in scheme is by David Madore from the blog entry Qu'est-ce qu'une machine hyperarithmétique ? .

  (define (ev prgm args) (if (not (list? prgm)) (error "prgm is not a list")) (let ((inst (car prgm))) (case inst ((0) args) ((1) (cadr prgm)) ((2) (+ (car args) 1)) ((3) (list-ref args (- (cadr prgm) 1))) ((4) (if (= (car args) (cadr args)) (caddr args) (cadddr args))) ((5) (let ((vals (map (lambda (p) (ev p args)) (cddr prgm)))) (ev (cadr prgm) vals))) ((6) (ev (car args) (cdr args))) (else (error "unknown instruction")))))

This defines a scheme function ev which takes two arguments, an Amycus program and an argument for the program, and returns the result of running the program. Amycus numbers are represented as scheme numbers, and Amycus lists and scheme lists in the natural way. This interpreter sometimes accepts invalid programs or arguments, in which some lists involved have extra elements, but this probably does not impact the integrity of the language in a significant way.

Notes

  • Amycus Severus is a restricted version of Amycus. Any Amycus Severus program is also a valid Amycus program, and if evaluating Amycus Severus is defined on a program and an input, then evaluating it as an Amycus program is also defined and has the same result.
  • Amycus Severus is Turing-equivalent. It can read and write any natural number, so it can compute any computable function from natural numbers to natural numbers.
  • You can prove this by translating multivariate lambda calculus expressions and Peano arithmetic to Amycus, as outlined in the Amycus article. All of that translation works unchanged in Amycus Severus.
  • Amycus Severus, however, cannot read or write arbitrary lists. Any Amycus Severus program can create lists of only a bounded size, can read only the first bounded number of elements of lists, and there are further restrictions on how it can access lists.
  • David doesn't give a name for this language, so User:B_jonas gave the name “Amycus Severus”.