Osis

Osis is a stack-based language specialized in sequences invented by User:A. Not only as in the commands, but also as in how it calculates the sequences. With smart memory usage and memorization, it can calculate several sequences within seconds of time, without getting a recursion error or memory overflow.

This removes trivial commands useful for golfing in Oasis just for getting a feeling of sequence-based programming.

What does a program look like?

Due to it's nature, you can only make a monadic program (which takes 1 argument). Let's see how the actual code looks like:

[code] [predefined base cases]

First, the predefined base cases (reversed) are taken off the actual code. These are used for the starting values for a sequence. One or more spaces separates the [code] segment from the [predefined base cases]; the same tokens act in the segregation of base case elements among each other. For example, the code:

{}+ 1 0

stands for:

a(n) = {}+
a(0) = 0
a(1) = 1

The explanation for the code {}+:

{   # a(n - 1)
 }  # Calculates a(n - 2)
  + # Adds them up

You probably already have guessed it :P. This calculates the Fibonacci sequence. It calculates n = 1000 in a split second.

The following Extended Backus-Naur Form (ENBF) description applies to the language's syntax:

program       := padding , formula , spaces , baseCases , padding ;
formula       := { command } ;
command       := unaryOp | binaryOp | sequenceRef | digit ;
unaryOp       := "_" | '"' | "|" | "$" | "!" | "," ;
binaryOp      := "+" | "-" | "*" | "/" | "%" | "^" ;
sequenceRef   := ";" | "{" | "}" | "(" | ":" | "`" ;
baseCases     := [ baseCase , { spaces , baseCase } ] ;
baseCase      := signedInteger ;
signedInteger := [ "+" | "-" ] , digit , { digit } ;
digit         := "0" | "1" | "2" | "3" | "4"
              |  "5" | "6" | "7" | "8" | "9"
              ;
padding       := [ spaces ] ;
spaces        := space , { spaces } ;
space         := " " ;

Where is the implicit input?

In Osis, input is pushed automatically and outputted implicitly.

Execution Principle

An Osis program operates in a perpetual loop, maintaining an integral index, or parameter, designated as n, the same commences with a value of zero (0) and increments utilizing a step size of one (1) upon each cycle's completion.

During each such iteration, the code segment is executed, if no base case for the sequence element expresses its amenability to the index n; otherwise the base case value is assumed verbatim.

Defined in a more formal diction, given the index n and the sequence a(i), the following pseudocode applies:

let n <- 0

repeat
  if baseCases(n) exists then
    a(n) <- baseCases(n)
  else
    a(n) <- execute the formula
  end if
  
  n <- n + 1 
end repeat

Examples

Factorial

`{* 1

Powers of 2

{" 1

Period [1,2]

This program generates a sequence composed of alternating 1 and 2 numbers:

`2%1+

Period [1,3]

This program generates a sequence composed of alternating 1 and 3 numbers:

21_`^-

Command reference

Here, a represents the current function. If a(0) is undefined, it is 0 by default.

Command	Description
_	Pops the top element from the stack, negates it, and pushes the result unto the stack.
"	Pops the top element from the stack, multiplies it by 2, and pushes the result unto the stack.
|	Pops the top element from the stack, divides it by 2, rounds it, and pushes the result unto the stack.
$	Pops the top element from the stack, squares it, and pushes the result unto the stack.
!	Pops the top element t from the stack, computes its factorial t!, and pushes the result into the stack.
,	Pops the top element t from the stack, computes the t-th prime, where t = 0 answers to the first prime number 2, and pushes the result unto the stack.
+	Pops the top element a and the new top element b from the stack, computes the sum a+b, and pushes the result unto the stack.
-	Pops the top element a and the new top element b from the stack, computes the difference a-b, and pushes the result unto the stack.
*	Pops the top element a and the new top element b from the stack, computes the product a*b, and pushes the result unto the stack.
/	Pops the top element a and the new top element b from the stack, computes the quotient a/b, rounds the same, and pushes the result unto the stack.
%	Pops the top element a and the new top element b from the stack, computes the remainder of the integer division a/b, and pushes the result unto the stack.
^	Pops the top element a and the new top element b from the stack, computes the power ab, and pushes the result unto the stack.
;	Pops the top element t, queries the sequence element a(n-t), where n constitutes the current iteration index, and pushes the term unto the stack.
{	Queries the sequence element a(n-1), where n constitutes the current iteration index, and pushes the term unto the stack.
}	Queries the sequence element a(n-2), where n constitutes the current iteration index, and pushes the term unto the stack.
(	Queries the sequence element a(n-3), where n constitutes the current iteration index, and pushes the term unto the stack.
:	Pops the top element t, queries the sequence element a(t), and pushes the term unto the stack.
`	Pushes the current iteration index n unto the stack.
0	Pushes the number 0 unto the stack.
1	Pushes the number 1 unto the stack.
2	Pushes the number 2 unto the stack.
3	Pushes the number 3 unto the stack.
4	Pushes the number 4 unto the stack.
5	Pushes the number 5 unto the stack.
6	Pushes the number 6 unto the stack.
7	Pushes the number 7 unto the stack.
8	Pushes the number 8 unto the stack.
9	Pushes the number 9 unto the stack.

Interpreter

• Common Lisp implementation of the Osis programming language.