SELECT.

From Esolang
Jump to: navigation, search

SELECT. is minimalistic esoteric programming language based on exponentials and logarithms. It is based on brainfuck, but replaces the usual operations of incrementation and decrementation with exponentials and logarithms, and replaces the usual unsigned integers with double-precision complex numbers held on each cell. Also, programming in it is very unlike programming in brainfuck, as the only operations which haven't been changed semantically from brainfuck are LEFT. and RIGHT. (brainfuck's < and >).

Etymology

The name SELECT. comes from the appearance of any programs in the language, with every single command written in uppercase letters and ending with a dot. SELECT. is also a command necessary to realize any operation in the language, by selecting the operators (with exception of conjugation).

Definition

A SELECT. program has a single data tape, where each cell carries a complex number. Cells are unbounded, and the tape is unbounded on both sides. Input\Output is done by using complex numbers as coordinates for the pixels in an graphical buffer. Operations in SELECT. are implemented using exponentials and logarithms, as well as numbers, which can't be directly typed into the language. For example, 1 is expressed as log(x) where the logarithm has base x.

Commands

Command Operation
RIGHT. Moves the data pointer 1 position to the right.
LEFT. Moves the data pointer 1 position to the left.
EXP. Takes the cell under the pointer to the power of the cell to be selected.
LOG. Applies the principal logarithm with base equal to the cell to be selected to cell under the pointer.
CONJ. Takes the complex conjugate of the current cell.
SELECT. Selects the cell under the pointer for operation.
Flow control
LOOP. Marks the start of a loop. Skips past the matching END marker if the real part of the value of the cell under the pointer is greater than the imaginary part.
END. Jumps back to matching LOOP marker.
I/O operations
PRINT. Prints a square at the x coordinate equal to the real part and y coordinate equal to the imaginary part of the value of the cell under the pointer.
COLOR. Sets the current output color according to the current cell, as specified below
GET. Waits for the user to click somewhere on the screen, then register the x and y coordinates as the real and imaginary part of the cell under the pointer.
CLEAR. Clears the buffer.

The scheme for converting cell values to colors follows:

  Red-value := |Re(x)|/256
  Green-value := |Re(x)|%256
  Blue-value := |Im(x)|%256

The program also starts with some additional information about the I\O buffer, which defines how dots will be displayed on the screen:

  (x, y, z) - Buffer definition
  x = Width of the buffer in buffer pixels (must be an odd integer)
  y = Height of the buffer in buffer pixels (must be an odd integer)
  z = Integer representing how big is an pixel in the buffer, each buffer
      pixel is a grid of z-by-z real pixels on the screen.

The printed pixel will be the nearest one to the indicated coordinates that is present in the buffer.

Constants

Every cell in SELECT. is initially set to a value k, which chosen at random uniformly in the range (1,1.0000001), but you can manipulate each cell so it gives a consistent answer each time you run the program. For example, to make the number 1, you write:

  LOG. SELECT.

So, basically what you are doing is to take the logarithm base k of k, and, because k is always positive and greater than one, the result will be always 1.

Examples

Natural numbers

Contructing natural numbers in SELECT. may require a lot more effort than in BF, because simpler operations must be implemented from more complicate ones, i.e. deriving addition and subtraction from exponentials and logarithms. Firstly, the number 2:

  EXP. SELECT. EXP. RIGHT. SELECT. LEFT. LOG. RIGHT. SELECT. LEFT. LOG. RIGHT. SELECT. LEFT.

So, how does it work?

  Step 1.
  TAPE k k k k k
  HEAD     A
  Commands: EXP. SELECT.
  Firstly, the zeroth cell is raised to the power of itself:
  Cell 0 = kˆk
    
  Step 2.
  TAPE k k k^k k k
  HEAD      A
  Commands: EXP. RIGHT. SELECT. LEFT.
  Then the cell is again raised to k, and the pointer returns to cell 0.
  Cell 0 = Cell 0 ^ k = (k^k)^k = k^(k*k) = k^(k^2)
  
  Step 3.
  TAPE k k k^(k^2) k k
  HEAD       A
  Commands: LOG. RIGHT. SELECT. LEFT. | LOG. RIGHT. SELECT. LEFT.
  The cell is applied the logarithm base k twice:
  logK(logK(Cell 0)) = logK( logK(k^(k^2)) ) = logK( (k^2) ) = 2

And by repeating step 2, one can get any other natural number similarly.

Negative One

Negative one can be introduced as:

  -1 = logK(logK^K(K))

Natural Base e

Many common computations (such as of the argument of a number) make use of the natural base e. Here is one way to approximate its value:

  y:=((2^2)^(2^2))^((2^2)^(2^2))
  e:=(1 + y^(-1))^y

This algorithm gives more decimal digits of accuracy than would be needed for most applications. (More than IEEE-754 can use.)

Addition and Multiplication

Two numbers can be multiplied using the rule:

  x * y = logK( (k^x)^y )

And added with:

  x + y = logK( (k^x)*(k^y) )

Now, division can be done by raising any number by -1, thus getting its inverse, and subtraction by multiplying by -1. One can take square, cube roots and so on by using fractions as the exponent, and all elementary operations are then defined in terms of exponents and logarithms.

Real Part and Imaginary Part

You can find the real and imaginary parts of a number using these rules:

  Re(x) = (x + conj(x))/2
  Im(x) = Re(-i*x) = (x - conj(x))/(2i)

Modulus and Argument

You can find the absolute value and argument of a number by using these rules:

  |x| = (x*conj(x))^(1/2)
  arg(x) = -i*ln(x/|x|)

Integer division and integer modulus

You can use the periodic nature of branch cuts to compute x%y for integers x and y, though the fact that standard cuts fall between numbers whose arguments are odd multiples of pi complicates the needed code:

    a := -1^(2/y)
    b := log_a(a^x) (this is where the branch cut happens: b will not equal x, but will be equivalent to it mod y)
  if -b*x<=0, x%y = b+x
  else x%y = b

Once you have the integer modulus, you can easily find the floored quotient (integer division):

  x//y = (x-x%y)/y

Trigonometry

  cos(x) = (e^(i*x)+e^(-i*x))/2 = Re(e^(i*x))
  sin(x) = (e^(i*x)-e^(-i*x))/(2*i) = Im(e^(i*x)) 
  tan(x) = sin(x)/cos(x)
  asin(x) = -i*ln((1-x^2)^(1/2)+x*i)
  acos(x) = -i*ln(x+(1-x^2)^(1/2)*i)
  atan2(y,x) = -i*ln((x+i*y)/(y^2+x^2)^(1/2))

And from these to the hyperbolic trig functions:

  cosh(x)=cos(i*x)
  sinh(x)=-i*sin(i*x)
  tanh(x)=-i*tan(i*x)
  arsinh(x)=-i*arcsin(i*x)
  arcosh(x)=-i*arccos(x)
  artanh(x)=-i*arctan(i*x)

Loop n times

The boundary condition for SELECT.'s loops is equivalent to "loop while pi/4<arg(x)<5pi/4". Thus, one can create an n-step loop where the current loop count is tracked by count thusly:

  sentinel:=(-1+i)/2^(1/2)
  step:=k*i^(1/n)
  LOOP on sentinel:
     count:=logK(|sentinel|)
     #do stuff
     sentinel*=step
  END on sentinel

Switch Statement

If one wants to perform different code for each of the possible values of x from 1 to n, it is space inefficient to use the above method to iterate through the values of x, since it will require about 2n+13 tape overhead. The following method will use a tape overhead of about 5 (total!) to do it:

  sentinel:=i^(1/4)
  step:=2^(1/n)
  foreach x in 1..n:
     LOOP on sentinel
        #do stuff
        RIGHT. LOG. SELECT. #set the next tape cell to 1
     END
     sentinel:=sentinel^step

Setting the current tape cell to 1 just before the end of the loop not only prevents the loop from repeating, but prevents all subsequent loops from being entered, as the value of sentinel will, in all subsequent iterations, be 1.

Note that in both of the last two code samples, the tape used by the omitted code ("#do stuff") should be constant and independent of anything, including the value of x, sentinel or any tape cells.

Computational class

The following proves SELECT.'s Turing-completeness by reducing Etre to it. It uses i for Etre's 1 and -i for Etre's 0. In fact, it proves that the LOG. EXP. SELECT. LEFT. RIGHT. subset of commands is Turing-complete, since it does not use CONJ. despite the fact that doing so would make the converted programs shorter and simpler.

Etre to SELECT.

TAPE CELL STRUCTURE: 1 k (1/2, i/-i, -1, 0/1)* k k k 0

Init:
    LEFT. LEFT. LOG. SELECT. RIGHT. RIGHT.
    MAKE I:

        MAKE 1/2:
        RIGHT. EXP. SELECT.
        EXP. LEFT. SELECT.
        RIGHT. LOG. LEFT. SELECT.
        LOG. RIGHT. SELECT.
        EXP. LEFT. SELECT.
        
        END MAKE 1/2
        
     RIGHT. 
        
        MAKE -1:
        RIGHT. EXP. SELECT.
        LEFT. LOG. RIGHT. SELECT.
        EXP. LEFT. SELECT.
        
        MARK AS makenumsign
        LOG. RIGHT. SELECT.
        LEFT. 
        END MAKE -1

     RIGHT. EXP. LEFT. SELECT.
     RIGHT. LOG. RIGHT. SELECT.
     LEFT. LEFT.     
        
     EXP. LEFT. SELECT.
     RIGHT. 
     END MAKE I

  EXP. RIGHT. SELECT. RIGHT. LOG. SELECT. RIGHT. RIGHT. RIGHT. LOG. SELECT. LOG. LEFT. SELECT.
  LEFT. LEFT. LEFT. LEFT. LEFT.



(:
EXP. RIGHT. SELECT. LEFT.
LOOP.



-: 
RIGHT. RIGHT. RIGHT. RIGHT. RIGHT. RIGHT.
LOOP.
EXP. SELECT. LEFT. LEFT. LEFT.
    
    MAKE I:

        MAKE 1/2:
        RIGHT. EXP. SELECT.
        EXP. LEFT. SELECT.
        RIGHT. LOG. LEFT. SELECT.
        LOG. RIGHT. SELECT.
        EXP. LEFT. SELECT.
        
        END MAKE 1/2
        
     RIGHT. 
        
        MAKE -1:
        RIGHT. EXP. SELECT.
        LEFT. LOG. RIGHT. SELECT.
        EXP. LEFT. SELECT.
        
        MARK AS makenumsign
        LOG. RIGHT. SELECT.
        LEFT. 
        END MAKE -1

     RIGHT. EXP. LEFT. SELECT.
     RIGHT. LOG. RIGHT. SELECT.
     LEFT. LEFT.     
        
     EXP. LEFT. SELECT.
     RIGHT. 
     END MAKE I

     EXP. RIGHT. SELECT. RIGHT. EXP. SELECT. RIGHT. RIGHT. RIGHT. LOG. SELECT. LOG. LEFT. SELECT.
     LEFT. LEFT. LEFT. LEFT.

  LOOP.
     LEFT. LEFT. LEFT. LEFT.
  END.
  RIGHT. RIGHT. RIGHT. RIGHT. RIGHT.
END.
LEFT. LEFT.
 
 
 
):
END.

Sample programs

Cat program

It's not exactly a cat program in the common sense of a programming language of writing down the text typed by the user, but it does copy its input to its output: The input is the position of a mouse click, and the output is a pixel on the screen at those same coordinates. The SELECT. cat program is like MS Paint, you just click anywhere on the screen and a black dot will appear there. There it is:

  LEFT. LOG. SELECT. LOG. RIGHT. SELECT. LEFT. LOOP. RIGHT. GET. PRINT. LEFT. END.

Hello World

The first Hello World! Program is too long for this page.

99 bottles of beer

The first 99 bottles program is too long for this wiki and the internet in general.

Implementation