text:
Generate a "Poem"
Given a strictly positive integer, N, produce an output satisfying the following:

Produce an array of length N.
Every string (i.e. "word") in the array is of length N.
Every letter in the word is unique.
Every first letter of the words are unique between each other.
The remaining items of each word are equal to each other.

Example output
For an input of e.g. 3:
cba
dba
eba

Specification

Trailing whitespace is totally allowed.
The "letters" don't have to be from the lowercase alphabet, as long as they aren't whitespace.
The maximum N you need to support is 13, since there are 26 letters in the lowercase alphabet.
The separator of your array can be anything, as long as you will never involve that character for every possible input from 1 to 13. You can also just output a literal array.
Letters have to be 1 character long.
Letters are case-sensitive, e.g. a and A can appear on the same line.

Can the "letters" be numbers?

Do the "letters" have to be only one character long?

still better than vogon poetry

Are upper and lower case letters considered to be different, so? e.g., can a and A appear on the same line?

Japt, 9 8 bytes
;ÆîEhCgX

Try it
;ÆîEhCgX     :Implicit input of integer U
 Æ           :Map each X in the range [0,U)
  î          :  Slice to length U
;  E         :    Printable ASCII
    h        :    Replace first character (space) with
;    C       :      Lowercase alphabet
      gX     :      Character at index X

Pyth, 9 bytes
V>QG+N<Gt

Try it online!

V>QG For each letter in the last Q (the input) elements of the lowercase alphabet:
+N>Gt Append that letter to the first Q-1 elements of the lowercase alphabet

For Q=13, the output looks like this:
nabcdefghijkl
oabcdefghijkl
pabcdefghijkl
qabcdefghijkl
rabcdefghijkl
sabcdefghijkl
tabcdefghijkl
uabcdefghijkl
vabcdefghijkl
wabcdefghijkl
xabcdefghijkl
yabcdefghijkl
zabcdefghijkl

The meaning behind this poem... so deep.

Charcoal, 11 bytes
ＮθＵＯθ⮌β↓…βθ

Try it online! Link is to verbose version of code. Explanation:
Ｎθ

Input N.
ＵＯθ⮌β

Print a square of size N filled with the reversed lowercase alphabet.
↓…βθ

Print the first N lowercase letters downwards.

C (gcc), 58 bytes
i,j;f(n){for(i=n;i;)putchar(j++?j>n?j=!i--,10:j+63:i+77);}

Try it online!

Python 2, 53 bytes
lambda n:['%xopqrstuvwxyz'[:n+1]%i for i in range(n)]

Try it online!
Chooses a hex digit (0123456789abc) for the first character, and the last half of the alphabet for the rest.

Another 53-byter that does the same thing, using map:

lambda n:map('%xopqrstuvwxyz'[:n+1].__mod__,range(n))

Try it online!

Another 53-byter, this time using Python 3 f-string:
lambda n:[f'{i:x}copqrstuvwxyz'[:n]for i in range(n)]

Try it online!

If numeric characters are not allowed:
Python 2, 58 57 bytes
-1 byte thanks to @dingledooper !

lambda n:['%copqrstuvwxyz'[:n+1]%(i+65)for i in range(n)]

Try it online!
Choose the first letter from the first half of the alphabet, and the last letters from the last half of the alphabet.

05AB1E, 10 8 bytes
AÂSìδ£I£

Try it online!
Haha! With the expert help of Kevin, I beat Pyth once again!
Explained (with Docs Descriptions)
A| 'abcdefghijklmnopqrstuvwxyz'
Â| Bifurcated a. Push a, reversed(a)
S| Cast a to a list of characters / digits.
ì| Merge b with a if both are lists, else prepend b to a. Push a.prepend(b)
δ| Outer Product. Get the next command and apply it double-vectorized.
£| Head. Push a[0:b]
I| Input
£| Head. Push a[0:b]

Your outputs are 1 character too long. The I should be I<. I do have the feeling 8 should be possible though, so I'll see if I can find something.

Yay, found an 8-byter after all: AÂSìδ£I£

JavaScript (Node.js), 74 bytes
n=>(q=`opqrstuvwxyz,`.slice(13-n)).replace(/./g,t=>i.toString(++i)+q,i=10)

Try it online!

As you don't use any stuff from Node libraries, consider changing it from JavaScript (Node.js) to JavaScript (ES6).

Retina, 38 26 bytes
.+
*.
Y`.`l
L$`.
$=
Y`a`Rl

-12 bytes thanks to @Neil
Try it online!
This works by generating the beginning of 'abc...' length N, then repeating it and substituting the first letter for something from 'zyx...'
.+         This converts the number into unary, using dots
*.         ^
Y`.`l      A cyclic transliteration: replace all dots with something from a-m
L$`.       Repeat per N with a line break at the end
$=         ^
Y`a`Rl     Finally, transliterate each 'a' with something from z-n

Oh, an actual use for the Y stage! An obvious saving is that all the lines will start with a, so there's no need to replace it with #, just transliterate the as directly. Then you can save a bit more by using the L$ stage to repeat rows by matching . and specifying a substitution of $=. (If not for that, the closing ) would have been unnecessary.)

Thanks! I don't know how I didn't realise the a thing, and I thought there must be a better way to repeat a line

Java (JDK), 83 bytes
n->{for(int i=n,j=0;i>0;)System.out.printf("%c",j++>0?j>n?10+(j=--i-i):j+63:i+77);}

Try it online!
I was able to make a one-liner, but it's 100 bytes long and works only on Java 13+ if that can inspire anyone to golf further...
n->(" %sNOPQRSTUVWXY".substring(0,n+2)).repeat(n).formatted((Object[])"ABCDEFGHIJKLM".split("",n+1))

Try it online!

dc, 52 bytes
[nAP1-d0<M]sL?dsnCo[d96+POO^OO^Bd*/-ODln-^/d0<L]dsMx

Try it online!
Input is on stdin, and output is on stdout.
Output for 13:
mBA9876543210
lBA9876543210
kBA9876543210
jBA9876543210
iBA9876543210
hBA9876543210
gBA9876543210
fBA9876543210
eBA9876543210
dBA9876543210
cBA9876543210
bBA9876543210
aBA9876543210

How it works:
[                     Start a macro.
 n                       Pop a number and print it.
 AP                      Print a newline.
 1-                      Decrement top of stack by 1.
 d0<                     If top of stack > 0,
 M                         then continue by calling macro M.
]sL                   End macro and save it in register L.

?                     Input number and push it on stack.
dsn                   Store top of stack in n.
Co                    Change output radix to base 12.

[                     Start a macro.
 d96+P                   Print the character with
                           ASCII code 96 + (top of stack).
                           (This will be a lower-case letter,
                           since 97 = 'a'.)
 OO^OO^Bd*/-ODln-^/      Push (12^12 - (12^12)/(11*11)) / (12^(13-n)).
                           In base 12, this is the leftmost n-1 digits
                           of BA9876543210 (or 0 for n=1).
 d0<L                    If this number > 0, call macro L to print it,
                           decrement the value of n at the top of stack,
                           and go back to the top of the loop M.
]dsMx                   End macro, save it in register M, and execute it.

B (asm2bf dialect), 136 bytes
p(c){asm("rclr1,r4");asm("outr1");}g(){asm("in r1");}n;c 65;d;i;main(){i=n=g();while(i--){p(c++);d=65+n;while(d-n-65<n-1)p(d++);p(10);}}

Output assembly:
#!/usr/bin/env bfmake
    stk 16
    org 0
db_ 0
db_ 65
db_ 0
db_ 0
#PAGE_SIZE = 16
#MM_BASE = 5
#call("alloc")
    mov r4, r6
#call("_main")
    end
@alloc
#alloc("r6", "r5")
    ret
@_p
    rclr1,r4
    outr1
    ret
@_g
    in r1
    ret
@_main
    psh 3
    psh 0
#call("_g")
    mov r2, r1
    pop r1
    sto r1, r2
    pop r1
    sto r1, r2
@L1
    mov r2, 3
    rcl r1, r2
    dec r1
    sto r2, r1
    inc r1
    jz_ r1, %L2
    psh r4
#call("alloc")
    mov r2, 1
    rcl r1, r2
    inc r1
    sto r2, r1
    dec r1
    sto r6, r1
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    psh 2
    psh 65
    rcl r1, 0
    mov r2, r1
    pop r1
    add r1, r2
    mov r2, r1
    pop r1
    sto r1, r2
@L3
    rcl r1, 2
    psh r1
    rcl r1, 0
    mov r2, r1
    pop r1
    sub r1, r2
    mov r2, 65
    sub r1, r2
    psh r1
    rcl r1, 0
    mov r2, 1
    sub r1, r2
    mov r2, r1
    pop r1
    lt_ r1, r2
    jz_ r1, %L4
    psh r4
#call("alloc")
    mov r2, 2
    rcl r1, r2
    inc r1
    sto r2, r1
    dec r1
    sto r6, r1
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    jmp %L3
@L4
    psh r4
#call("alloc")
    sto r6, 10
    mov r4, r6
#call("_p")
#free("r4")
    pop r4
    jmp %L1
@L2
    ret

Ruby, 47 bytes
->n{a=*?`..?z;(1..n).map{|i|a[i]+a[14,n-1]*''}}

Try it online!

Bash + Unix utilities, 62 59 bytes
dc -e'[nAP1-d0<M]sL?dsnCo[d96+POO^OO^Bd*/-ODln-^/d0<L]dsMx'

Try it online!
Input is on stdin, and output is on stdout.

Here's the original, longer answer:
echo {a..m}`echo {o..z}|tr -d \ `|fold -14|cut -b 1-$1|sed $1q

Try it online (62 bytes)
Input is passed as an argument, and output is on stdout.

Perl 5 -na, 42 bytes
say$_,(A..Z)[0..$F[0]-2]for(N..Z)[0..$_-1]

Try it online!

Nice! Had basically the same! :) You can save a few bytes using "@F" instead of $F[0] and reorganising the letters a bit (to avoid arithmetic): Try it online!

Befunge-93, 53 51 bytes
&:v
< <>::      v:::\,+*77:
|  ^-1,+*88<_$$\1-0.:
@

Try it online!
0 is my two character delimiter. Outer loop outputs N'+(7*7) in ascii, sets M to N (this requires a swap) then enters inner loop. Inner loop outputs M+(8*8) in ascii and decrements M. On exiting inner loop outputs 0 and decrements N' (this requires a swap).  | and _ are the loop condition instructions respectively. : is often used to make copies since most operations - from arithmetic to conditional check, destroy the value they operate on by popping it out of the stack
Befunge is stack based with a single instruction pointer that points to a character in the code. It has a travelling direction that can be changed via arrows <>^v
Befunge-98 submission by ovs, 43 bytes
&:>:77*+,\:>:: v
.:|;-1,+*8;^;8<_$$\1-0
  @

Try it online!

There's wasteful spaces that a better golfer could probably get rid of

43 bytes by removing most of the spaces from the 53 byte version: https://tio.run/##S0pNK81LT9W1tPj/X83KzsrcXEtbJwbIsFIo49KzqrHWNdTR1rKwjrO2sIlXUYkx1DXgUlBw@P/fBAA

You can use ' to push integers like 64 and 49 with just two bytes.

@ovs Oh, I was looking at the specification on wikipedia which was for Befunge-93 (when writing my answer), didn't notice the difference. Should I edit your answer in or change mine to 93? Also I didn't understand what ' does in befunge-98

' pushes the character value of the next cell on the stack. An example: '@ pushes 64 on the stack. (A complete funge-98 specification can be found at https://quadium.net/funge/spec98.html)

@ovs Nice, makes sense. Would you prefer I edit my answer to include yours, or change the title of mine to befunge-93 then you can post yours separately if you like

Its up to you what you do with your answer. You can edit my golf in, have both versions or just keep it like it is. I won't post this as my own, since I only looked at the control flow, I don't even fully understand what this actually does.

@ovs I've added both then. Feel free to post your own answer if you change your mind :p

Husk, 14 12 11 bytes
←ẊM:M↑½…"az

Try it online! Splits the alphabet into two halves, truncates each half to the size of the input, and then recombines them in the proper way.

Google Sheets, 76 bytes
=ArrayFormula(Char(Row(Offset(78:78,,,A1)))&Join(,Char(Row(Offset(65:65,,,A1

When you exit the cell, Sheets will automatically add the 5 trailing parentheses. Input is in cell A1. Output is wherever you put the formula and the N-1 cells below it.
Row(Offset(78:78,,,A1)) gives us an array from 78 to 78+N-1.
Char(Row(~)) turns that array into their ASCII equivalent (capital letters).
Char(Row(Offset(65:65,,,A1))) does the same thing for the range 65 to 65+N-1.
Join(Char(~)) combines that second array into a single string.
ArrayFormula(~) makes these functions input and output arrays instead of a single value.

[MATLAB/Octave], 35 bytes
char([N+[1:N]',ones(N,1)*[1:N]]+64)

First create a column vector ranging from N+1 to 2N with N+[1:N]. Make a column vector with all values equal to one and length N, and multiply by a row vector containing values 1 to N to make a matrix of N columns with all rows equal to 1:N. Concatenate the first vector with your matrix, add 64 to all digits and use char to turn every row into a string.

C (gcc), 98 88 bytes
-10 thanks to @ceilingcat
c,d,i,j;f(n){for(c=65,i=n,d=c+n;i--;puts(""))for(j=!putchar(c++);j<n-1;)putchar(d+j++);}

Try it online!

86 bytes by removing the (as far as I think they are called in this terrible version of C) forward declarations of c,d,i: Try it online! (I'm also not sure why you are compiling with -Dp=putchar)

it's a leftover; I probably forgot to remove it

Why not d=78?

Suggest ~j+n instead of j<n-1

73 bytes (I changed almost everything though, not sure whether I should post this as my own answer): Try it online!

Feel free to post it as your own answer, probably it's deserved :p

Jelly, 9 bytes
Øa;€Ṛ$ḣḣ€

A monadic Link accepting an integer in \$[1,13]\$ which yields a list of lists of characters.
Try it online!
How?
Øa;€Ṛ$ḣḣ€ - Link: integer, N
Øa        - lower-case alphabet
     $    - last two links as a monad:
    Ṛ     -   reverse (the alphabet)
  ;€      -   concatenate that to each of (the alphabet)
      ḣ   - head to index (N)
       ḣ€ - head each to index (N)

JavaScript (Node.js),  66  60 bytes
f=(n,k=n*n)=>k?Buffer(k--%n?[97+k%n]:[10,123-k/n])+f(n,k):''

Try it online!

Haskell, 34 bytes
(\t->t.(:['n'..])<$>t['a'..]).take

Try it online!

CJam, 22 bytes
'[,65>_W%qi<_,(@<am*N*

Try it online!
This works by generating the Cartesian product of the each of the last n characters of the alphabet and a singular array containing a string with the first n-1 characters of the alphabet. For example, the following is outputted for 13:
ZABCDEFGHIJKL
YABCDEFGHIJKL
XABCDEFGHIJKL
WABCDEFGHIJKL
VABCDEFGHIJKL
UABCDEFGHIJKL
TABCDEFGHIJKL
SABCDEFGHIJKL
RABCDEFGHIJKL
QABCDEFGHIJKL
PABCDEFGHIJKL
OABCDEFGHIJKL
NABCDEFGHIJKL

Poetic, 360 bytes
absently,i jot out words,A-Z
moving a pen mindlessly about a page
i am making my art,i`m doing a poem
i ensure i can never do patterns at first
i`d alter a chr i am using
i`d say i am not consistent,cause i`m using a perfect copy i forged when i end a certain verse
o yes,i reckon i am doing A-Z lazily
o yes,i admit
o yes,i am silly
i compose tripe,o yes i do

Try it online!
This works by filling the entire memory with the negative of the inputted number (as that's the shortest way to copy it to multiple cells), then outputting the first character - which is decremented each iteration - and then the last few ASCII characters up to ASCII 255.
Warning: this takes a long time to run, even for small inputs. Such is the price to pay for a short length.


text:
Omit needless spaces for me
A great Python golfing tip is to omit needless spaces. But if you are like me, you don't always have the time to search for which spaces to remove. If only there was a way to speed up the process...
Task
Given a single line of Python, as input, return/output a new line which omits all needless spaces. The table below shows which spaces are needless, and must be removed for maximum golfage.
   | L D S
---+-------
 L | s s n
 D | n - n
 S | n n n

First token is row, second token is column
L: Letter
D: Digit
S: Symbol

s: space
n: no space
-: never happens (except multidigit numbers)

Clarifications

What is considered a letter, digit, and symbol?

Letter: _ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
Digit: 0123456789
Symbol: !"\#$%&'()*+,-./:;<=>?@[]^`{|}~

You can assume that all characters in the input are either a Letter, Digit, Symbol, or Space.
You can assume that there will be no such test case where two digits are separated by one or more spaces
You can assume that all test cases contain valid Python syntax
You can assume that there will be no leading or trailing spaces.
Follow the above rules for omitting spaces, regardless of whether omitting them will produce incorrect or different code

Test Cases
Input
print ( "Hello, World!" )
eval("eval('eval(`1`)')")
_  =  '_  =  %  r  ;  print _  %%  _'  ;  print _  %  _
[ 1for _ in range(10, 6 , -1)     ]
print 16

Output
print("Hello,World!")
eval("eval('eval(`1`)')")
_='_=%r;print _%%_';print _%_
[1for _ in range(10,6,-1)]
print 16

This is code-golf, so the shortest code in bytes wins!

Related fact: you can delete any space after a complex number literal (which ends with j); Python tokenizes e.g. 1jfor (1j for) and 1jor (1j or) without problem.

You can assume that all characters in the input are either a Letter, Digit, or Symbol - for completeness you may want to add Space. Code that does nothing is valid otherwise.

@JonathanAllan Now clarified that there will be no leading or trailing spaces in test cases.

Nice problem, but would have been much more fun if we had to skip strings.

Retina 0.8.2, 22 21 bytes
Saved a byte thanks to a mysterious hint from @Neil :P
(\d|\W) +
$1
 (\W)
$1

Try it online!

I can actually shave a byte off that... I'll keep you in suspense for a bit.

I think @Neil should just randomly post that exact comment on people's answers (with no idea in mind) just to inspire them :D

@GregMartin Eerie, as I had a completely different idea in mind anyway. I like his approach though, since the first stage ensures that there are no runs of spaces remaining.

I like his/her approach as well (and the attribution phrasing)  :)

JFTR, my 21-byte answer was
+`(\d|\W) | (\W)
$1$2

JavaScript (ES9),  60  43 bytes
s=>s.replace(/(?<![a-z_] *) | (?=\W)/gi,'')

Try it online!

I think porting @Abigail's Perl answer saves you a byte, even after using [^\d\W].

Java (JDK), 48 bytes
s->s.replaceAll("(?<![a-zA-Z_] *) | (?=\\W)","")

Try it online!
Port of Arnauld's JS answer.

perl -p, 24 27 26 bytes
s/([_\pL] ) +(?=\w)| /$1/g

Try it online!
This replaces any letter or underscore + space combo, which is followed by letter, digit or underscore, by itself, and removes any other space. In effect, it keeps any space which is proceeded by a letter or an underscore, and is followed by a letter, digit or underscore, and removes any other space. The (?=\w) is a lookahead, and won't be consumed by the matcher; this makes cases like _ _ _ _ _ keep all the spaces.
This will not work correctly for input containing characters outside of the ASCII range.

This seems to break if you add a few extra spaces betweenin and range in the 4th test case

Indeed. Should be fixed now.

Can't you just use a space instead of \s?

Of course. I probably just wrote \s* out of habit.

Charcoal, 41 bytes
≔ωη≔ωζＦθ≡ι ≔ηζ«×ζ№⁺_⭆⁶²⍘κφιι≔ωζ≔× №⁺_α↥ιη

Try it online! Link is to verbose version of code. Explanation:
≔ωη

Set h to the empty string. This variable is a space if the last non-space character was a letter.
≔ωζ

Set z to the empty string. This variable is a space if the last character was a space and the last non-space character was a letter.
Ｆθ

Loop over the characters of the input.
≡ι ≔ηζ«

If the current character is a space then copy h to z, otherwise:
×ζ№⁺_⭆⁶²⍘κφι

If the current character is a letter or digit then output z.
ι

Output the current character.
≔ωζ

Set z to the empty string.
≔× №⁺_α↥ιη

Set h to a space if the current character is a letter, otherwise set it to the empty string.

Befunge-93, 285 bytes
>~:1+!#@_11g\v>>,>>>>0>11p
v #          <>  ^
>:" "-#v_ \1` |
v      <      >      2^
>:"/"`#v_>    >^
v      <
>:"9"`#v_ \2- |
v      <      >" ",,^
>:"@"`#v_^
v      <      >    >,1^
>:"Z"`#v_ >\2-|
v      <      >" ",^
>:"_"-#v_ ^
v      <
>:"`"`#v_^
v      <
>:"z"`#v_ ^
       > ^

Try it online!
This is a simple statement machine, using a single 3 valued state (written to position (1,1)). The state is 1 if the previous character was a letter or underscore, 2 if the previous character was a space, and the last non-space character was a letter or underscore, and 0 otherwise.
The program reads one character at a time, ending the program if there is no more input; the read character is pushed on the stack. We then push the current state on the stack, and swap the two elements on the stack. We go through a bunch of if/then/else statements, to find out what kind of character we have (digit, letter or underscore, space, other symbol). If the current character is a digit, letter or underscore, and the current state is 2, we print a space. We then print the current character, unless that character is a space. Finally, we push the new state on the stack, which we then store on position (1,1), and we enter the loop again.

Jelly, 27 bytes
eþØW,ØD¤
+⁹n⁶¤Tị
Ñ>/ŻçµÑSḊç

A full program which accepts a Python formatted string of Python code which prints the result.
Try it online! (Do note that Jelly evaluates its arguments as Python before using them.)
How?
eþØW,ØD¤   - Link 1: list of characters, A          e.g. "_ 5 ;"
       ¤   - nilad followed by link(s) as a nilad:
  ØW       -   word characters                           "A..Za..z0...9_"
     ØD    -   digit characters                          "0...9"
    ,      -   pair                                      ["A..Za..z0...9_, "0...9"]
 þ         - outer product using:
e          -   exists in?                                [[1,0,1,0,0], [0,0,1,0,0]]

+⁹n⁶¤Tị    - Link 2: list of integers, X; list of characters, Y
    ¤      - nilad followed by link(s) as a nilad:
 ⁹         -   chain's right argument, Y
   ⁶       -   the space character
  n        -   not equal? (vectorises)
+          - add (to X)
     T     - truthy (non-zero) indices
      ị    - index into (Y)

Ñ>/ŻçµÑSḊç - Main Link: list of characters, S
Ñ          - call next Link as a monad -> Link_1(S)
  /        - reduce by:
 >         -   is greater than (gives 1s where letters are, 0s elsewhere)
   Ż       - prepend a zero
    ç      - call last Link as a dyad -> Link_2(that, S)
     µ     - start a new monadic Link:  (call that R)
      Ñ    - call next Link as a monad -> Link_1(R)
       S   - sum (gives 1s at letters, 2s at digits, 0s elsewhere)
        Ḋ  - dequeue
         ç - call last Link as a dyad -> Link_2(that, R)
           - implicit print

First removes spaces which do not directly follow letters, then removes remaining spaces which are not directly before letters or digits.

Python 3, 60 bytes
lambda s:re.sub(r' +(?=\W)|(?<![a-zA-Z_]) +','',s)
import re

Try it online!
Port of Arnauld's JavaScript answer.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Build a Turing *incomplete* language
The world is full of Turing-complete programming languages.  Just about every useful language (and most useless ones) are Turing-complete.  Some even became Turing-complete by accident.  Often this is great, since every Turing-complete language supports the same power of universal computation.  But the power of Turing completeness also comes with a curse!  The halting problem is undecidable for arbitrary programs in a Turing-complete language, and more generally, it’s impossible to analyze arbitrary programs in any non-trivial way.  Sometimes we need less powerful languages.
It takes great care to design a useful language that falls short of Turing completeness.  That’s the subject of this challenge!
Requirements
Write an interpreter that will accept a program and some input for the program, and produce some output.  The program, input, and output are given using simple data types of your choice.

Examples of “simple” data types: booleans; numbers; strings (bytes or Unicode); arrays or mappings of simple data types; algebraic data types defined in your interpreter.
Examples of data types not considered “simple”: function expressions; a subset of strings representing valid programs in some language (unless the subset is validated by your interpreter); generalized algebraic data types.  (This restriction is intended to disqualify trivial answers such as the identity function in Agda.)

Your input format must include some way to express arbitrarily sized natural numbers, in a reasonable representation of your choice (e.g. arrays or strings of unary, binary, or decimal digits, or directly as big integers if your host language has them).  Your output format must include at least two values, distinguishable from each other, to represent “true” and “false”.  Whether the formats can express anything else is up to you.
You may interpret programs in any target language, existing or new, under three conditions:

Your interpreter must be observably deterministic: for a given program and input, you must always produce the same output.
Your interpreter must not be Turing-complete.  Explain why this is the case—for example, it might be Turing incomplete because the interpreter eventually halts on every program and input, or because its halting problem is otherwise decidable.
As a minimum standard of usefulness, your target language must be able to express every polynomial-time function from natural numbers to booleans.  Explain why this is the case.  (To be clear, “polynomial-time” is defined over the length of the input in binary bits, even if your chosen representation of naturals is less efficient.)

Whether any other functions are expressible is up to you—for example, you might design your language around the primitive recursive functions, the elementary functions, or Gödel’s System T, each of which includes all polynomial-time functions.
Your interpreter may be written in any existing host language.  You may assume it runs on an ideal machine with unlimited memory and pointers big enough to access it.
This is code-golf: make the shortest interpreter you can!
Clarifications
I believe these points follow from the requirements, but they’re listed here in the hope of being helpful.  Feel free to request additional clarifications in the comments.

As per our default rules, your interpreter will be a program or function that follows our usual conventions for input and output.  However, programs in your target language are not bound by these rules—for example, if you decide that programs in your target language will be snippets that perform I/O by accessing a predefined variable, that is fine, as long as your interpreter translates this convention by (say) automatically reading from STDIN to the variable at startup and writing the variable to STDOUT at exit.  (This can be viewed as a natural consequence of our policy that languages are defined by their interpreters.)
You may of course use any data types you want within your language, as long as the program, input, and output types are simple data types.
Your interpreter must be prepared to accept anything in your chosen simple data type for programs as a program.  Your interpreter may of course perform extra validity checks on the program and throw errors or fall back to some default behavior or do something else that respects the requirements—but you may not impose extra validity constraints on programs purely at the specification level.  Writing “eval but you’re not allowed to pass in anything except deterministic programs that halt” does not solve this challenge.
Because of the determinism requirement, an interpreter that works by executing arbitrary code with a timeout in seconds is unlikely to be valid.  (Doubly so if it leaves programs enough wiggle room to disable or evade the timeout in some underhanded way.)
Although I am willing to be may already have been proven wrong, my expectation is that solving this challenge will require doing some actual work to interpret a language.  I’m not looking for solutions that put in 1% of this work to satisfy 80% of the requirements, whatever that means—that wouldn’t be fair to those who put in the effort to solve the full challenge as written.
I updated the challenge with a requirement for the representation of natural number inputs to be “reasonable” after realizing there was a loophole using an unreasonable representation of naturals.  Specifically: if we enumerate all polynomial-time functions as \$p_0, p_1, p_2, \dotsc\$, the unreasonable representation of \$n \in \mathbb N\$ as \$(p_0(n), p_1(n), \dotsc, p_{n-1}(n))\$ allows any polynomial-time function \$p_m\$ to be “programmed” as \$\{0 \mapsto p_m(0), 1 \mapsto p_m(1), \dotsc, m \mapsto p_m(m), n \mapsto n_m\text{ for }n > m\}\$, with every output hard-coded into either the program or the input!  (I don’t think any of the existing answers have tried to exploit such an unreasonable representation.)

Related challenges

Write a Programming language of Unknown Completeness
Turing-Complete Language Interpreter
Design a One Instruction Set Computer!
Fewest (distinct) characters for Turing Completeness
Escape from the tarpit

(Deleted sandbox post)

Roughly related, and an answer that implements computationally equivalent subset of LOOP. Also there's a mathematical equivalent of PSPACE which looks deceptively simple.

@Bubbler Yes, I thought of reusing that mini-LOOP language (with the reduction you suggested at the time), and I might still, but I think it’s more interesting to do something new.

A possible loophole: what prevents is from saying "Programs that don't halt within a finite amount of time are ill-formed" and making the interpreter do undefined behaviour on them, and the interpreter is eval?

@mypronounismonicareinstate That would be covered by “Examples of data types not considered “simple”: … a subset of strings representing valid programs in some language (unless the subset is validated by your interpreter)”. You may not arbitrarily disallow some programs except by having your interpreter actually check for them. (The particular check of “halts within a finite amount of time” would be impossible, of course.)

Prime example: A sequence of non-recursive SQL statements including CREATE and ALTER table. It's rather hard to show it's not Turing complete other than by showing it won't halt. I was able to get so much done in SQL alone without reaching for TSQL WHILE.

Can I write a program that enumerates all primitive recursive functions, and the programmer inputs his program by inputting the position of the function which corresponds to his program in this list?

Also can I write an interpreter as follows: Take a python program as input, terminate if anything fancy is found (loops, functional programming, goto etc), and the only fancy thing allowed is for i in range(integer), and finally use eval?

@ghosts_in_the_code Yes (assuming the program type is a big integer). Yes, probably (assuming you explain why your checks are sufficiently restrictive and why the remaining language fragment is sufficiently powerful).

My theoretical computer science knowledge is a bit rusty. But if the language needs to be able to handle arbitrarily sized natural numbers, and needs to be able to represent all polynomial functions, doesn't it necessarily needs to be Turing-complete? Isn't it impossible to handle arbitrarily sized natural numbers without being Turing-complete?

@fishinear No. See the numerous links I provided, especially this section. (Also, a polynomial function is different from a polynomial-time function.)

Does anyone know whether regular expressions can calculate all polynomial time functions?

Python 2, 38 bytes
lambda s,n:s.strip("()+*%n")or eval(s)

Try it online!
This evaluates a subset of Python 2 given by arithmetic expressions using only characters ()+*%n, acting on natural-number input n. This computes the class ELEMENTARY, as the closure of the expressions in the basis
\$\{n+m, n^2, n\bmod m, 2^n\}\$
as noted in the Wikipedia article on ELEMENTARY and proven in Superpositions of elementary arithmetic functions. This moreover shows that Python operators can not only do primality testing, but any polynomial-time computable function.
The paper's argument seems to be based on constructions similar to Lopsy's prime-testing solution, encoding lists as digits in a large base and expressing bounded summation on those elements via arithmetic operations. The proof uses this expression for binomial coefficients as an intermediate step.
We check that our operators can express all operations in the basis. The +, **, and % operators do addition, exponent, and modulo. We can get the \$2\$ for \$n^2\$ and \$2^n\$ as \$2=0^0+0^0\$, where \$0\$ is n**n%n**n, avoiding the modulo-by-zero that simply n%n would give for n=0. Parentheses allow arbitrary composition of sub-expressions, and projection is trivial. We can interpret outputs as Booleans by associating True=1, False=0, as is standard in Python.
To ensure we that only this subset can be evaluated, we check that the input expression s is limited to the characters ()+*%n by stripping them from s and returning what remains if non-empty. Note that an invalid string is never evaluated, rather than evaluated then discarded, preventing it from anything strange it could call or overwrite to allow its output to escape.
The really isn't anything extra that's non-trivial that can be done with the whitelisted characters that we might worry allows Turing completeness. The letter n alone can't spell any function or keyword. We can get multiplication with *, but this is of course elementary. We can't even get negative numbers or floats, though these would still be harmless. We can get the empty tuple (), but nothing interesting can be done with it.

This is a really cool and surprising fact!  I wanted to see what an eval-free answer would look like, though I ended up using Javascript instead of Python. https://codegolf.stackexchange.com/a/204976/78112

I commented something similar on the post an hour earlier. Nice job :)

@ghosts_in_the_code Your comment involved for loops, which this answer does not—that’s what makes this so surprising.

@AndersKaseorg makes sense. Not stealing credit :)

APL (Dyalog Unicode), 15 14 bytes
(⍎⍞~'⎕⍎⍣⌶?{')⎕

Try it online!
A full program that takes two inputs (an array of numbers in APL syntax, and then a line of APL code) from STDIN and prints the result to STDOUT. The given APL code is sanitized by deleting characters that have a possibility to invoke an unbounded loop/recursion or access to the external system.
Since the input function is written in a single line, it must necessarily consist of built-in functions and operators, possibly including assignment. Using dfns is banned by the character {, and tradfns cannot appear because a tradfn requires at least two lines of code to be defined. Control structures and the Branch primitive are only meaningful inside trandfns, so they are automatically banned as a side effect.
The summary of banned characters with reasons:

⎕ by itself is used merely as an I/O primitive, but it is used as the first character of all the system functions, which include shell and filesystem access.
⌶ is called an I-beam, which grants access to experimental features. Some of the features include access to system.
{ is required to create a dfn/dop, and has no other uses.
⍣ is power operator, which can act as a for-loop or a while-loop depending on how it is used.
? is random number generator. It is excluded to satisfy the determinism requirement.
⍎ is APL's eval. I can't think of a hole accessible via ⍎ when ⎕UCS, ⎕AV etc are banned, but it is included to be safe.

Any one line of APL code without the six characters is guaranteed to terminate, thus it is not Turing-complete.
Here is a more formal proof via structural induction. Here is the list of all language elements for reference. Let's define a Q-function to be a function that terminates by returning a deterministic array or erroring in finite time.

All primitive functions except ⍎? along with bracket indexing are Q-functions.
All primitive operators except ⍣⌶ become Q-functions when given Q-functions and/or arrays as operands.
Tacit functions made of Q-functions are Q-functions, because tacit functions cannot express recursive functions. Also, something like g←⊢,g does not create a self-reference; it is either illegal (if g is not defined beforehand) or creates a new function based on the previous value of g.
Any variable created/modified via assignment can only result in a Q-function or an array.

The remaining functionality can be proven to be powerful enough to express elementary functions: Taking multiple arguments as a single array (e.g. subtraction function f(x,y) takes a length 2 array),

Zero = -⍨, Successor = 1∘+, and Subtraction = 0⌈-/.
Projection can be expressed as an indexing via ⊃.
Composition can be written as h g1,g2,g3,...
Bounded summation and product can be implemented as tacit functions: summation is +/(0,⍳∘⊃)(g,)¨∘⊂1∘↓ and change +/ to ×/ for product.

I’m not familiar with APL (maybe this is as good an excuse as any to start learning…), but are you sure you can’t get unbounded recursion through some back-door construction without direct self-reference, like (λx.x x)(λx.x x) in lambda calculus?

@AndersKaseorg It doesn't work because "functions" can only take arrays as args and return arrays, and "operators" can only take functions/arrays as operands (and nothing can take operators as args/operands).

Do control structures present a problem, or are they already somehow disallowed in this context?

@AndersKaseorg They are part of tradfn syntax (cannot appear outside a tradfn), and a tradfn requires at least two lines of source code to be defined. This submission only takes single line as input, so they are automatically disallowed.

What is stopping people from using gotos (starting a line with a label and going to that line, like A:→A to make a loop)?

@Wezl Both the label marker A: and the goto branch →A work only inside tradfns (and tradfns are not allowed as I already explained). Other than that, → has no meaning except for an interactive environment (e.g. Dyalog IDE).

Heh, in 18.0, this becomes invalid, because ⍎ now allows control structures.

APL (Dyalog Unicode), 42 bytes
{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}

Try it online!
I thought I'd give it a go at a more "proper" submission. This function interprets the programming language LOOP represented as a nested numeric array (which is used like an ADT), and the input to the LOOP program is represented as a simple numeric vector (enclosed once, for the sake of code golf).
The concept
LOOP has four kinds of commands: (x_i are variables and P are sub-programs)

x_i := 0 (zero)
x_i := x_i + 1 (increment)
P_1; P_2 (sequence)
LOOP x_i DO P END (bounded loop): Run P x_i times.

Here I represent a sequence of commands as an array [P_k P_k-1 ... P_2 P_1] instead of explicit concatenation, therefore eliminating a command. The order of command is reversed for the sake of code golf.
Each command in the program is encoded as a (c i) pair, where i is the variable index to refer to and c is the command to run on it. I use c←0 for zero, c←1 for increment, and c←P for the bounded loop.
For an illustration, the pseudocode
x_2 += x_1 * 2; x_1 = 0

can be written in LOOP as
LOOP x_1 DO
  x_2 := x_2 + 1
  x_2 := x_2 + 1
END;
x_1 := 0

and the representation for my submission is
(0 1)(((1 2)(1 2))1)
      ------------    Increment x_2 twice
     ---------------  Loop x_1 times
-----                 Assign zero to x_1

For the computational power, LOOP can precisely represent primitive recursive functions, thus satisfying the requirement of the challenge.
The code
{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}  ⍝ ⍺←Program; ⍵←Input
{                                     ⍺,⍵}  ⍝ Append ⍵ to ⍺ for reduction
 ∇{                                 }/      ⍝ Reduce, exposing the self reference to inner dfn:
       c i←⍺               ⍝ Extract command type and index from the next command
   ×|≡⊃     :              ⍝ If the command type is not simple (a loop subprogram):
             ⊃c⍺⍺⍣(i⊃⍵)⊃⍵  ⍝ Run the subprogram c x_i times on the state ⍵
                         ⋄            ⍝ Otherwise
                          c(⊣+×)@i⊢⍵  ⍝ Multiply c and then add c to x_i, which is equivalent to
                                      ⍝ If c is 1, add 1 to x_i; if c is 0, set x_i to 0

JavaScript (Babel Node), 59 51 47 bytes
n=>g=([a,b,c])=>c?g(a)+g(b)**g(c):b?g(a)%g(b):n

Try it online! (51 bytes thanks to @user202729)
This is using @xnor's basic approach, but without eval, and with a reduced basis.
The simple datatype D is a BigInt or an array of D.  Given a program p (a D) and an input n (a BigInt), the expression e(n)(p) interprets the program with input n.  Programs are interpreted as follows:

[a, b, c] evaluates a, b, and c, returning a + b**c
[a, b] evaluates a and b, returning a modulo b
[0] returns n

These three operations are enough to compute anything elementary recursive.  No matter the value of n, the value of n+n**n is positive, hence (n+n**n)%(n+n**n) gives 0, and 0 + 0**0 gives 1.  Hence, we have addition as a + b = a + b**1 and exponentiation as a**b = 0 + a**b.
For example, this is a program that computes the constant 2:
[[[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]],
 [[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]],
 [[[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]],
  [[[0], [0], [0]],
   [[0], [0], [0]]]]]

Corollary 2 of the following paper, which @xnor cited, is that this language gives all elementary recursive functions, using the usual tricks to encode a function \$\mathbb{N}^n\to\mathbb{N}\$ as a function \$\mathbb{N}\to\mathbb{N}\$.
Marchenkov, S. S. (2007). Superpositions of elementary arithmetic functions. Journal of Applied and Industrial Mathematics, 1(3), 351–360. doi:10.1134/s1990478907030106
They also point out in Corollary 3 that every recursively enumerable subset \$S\$ of \$\mathbb{N}\$ has an indicator function \$f:\mathbb{N}\to \{0,1\}\$ that is of the form \$f(n)=\exists z\in\mathbb{N},n=p_1(z)\wedge n=p_2(z)\$, where \$p_1(z)\$ and \$p_2(z)\$ are functions in the above language, such that \$f(n)=1\$ if and only if \$n\in S\$.  The argument is that you take a Turing machine that describes \$S\$ (say, as a nondeterministic machine that halts with elements of \$S\$ on the tape) then use the language to make nearly identical functions \$p_1\$ and \$p_2\$ that take an execution trace \$z\$ and check whether it brings the machine into a halt state, and if so the result of each function is the tape contents, and otherwise they result in \$p_1(x)=0\$ and \$p_2(x)=1\$.

“Python is too careful with its arithmetic (there are exceptions when doing mod-by-zero)”—there’s nothing inherently wrong with that. “All recursively enumerable functions”—you mean elementary functions (some recursively enumerable functions aren’t even computable).

@AndersKaseorg It's a problem with the approach I took to golf the interpreter, which is to evaluate all four functions in an array then select; I couldn't think of a short way to guard the division that would use a comparable number of bytes, that's all.  For the second thing, I misunderstood what Corollary 3 was saying; it's just the fact that verifying that a Turing machine follows a given execution trace is elementary recursive, and thus can be implemented as a "diophantine representation" using these integer operations.

51 bytes

Side-comment to @AndersKaseorg which doesn't affect your actual point. You wrote: "some recursively enumerable functions aren’t even computable".  Since "recursively enumerable" is a property that applies to sets, presumably this is identifying a function $f$ with ${\langle x,y\rangle \mid f(x)=y}.$ Usually "function" in this context would mean "total function"; but any r.e. function is then recursive. If you allow partial functions, then any r.e. function is partial recursive. Is there an interpretation that would give you an r.e. function that isn't computable in an appropriate sense?

@MitchellSpector The challenge asks only about functions from naturals to booleans, so I had interpreted the language “recursively enumerable functions” from the old version of this answer as “indicator functions of recursively enumerable sets”. Interpreting it as “recursive functions” (total or partial) wouldn’t have made the statement true either. The statement has since been corrected.

@AndersKaseorg Yes, the phrase "recursively enumerable function" isn't a standard usage, so it would require an explanation (or else it's just a mistake or misunderstanding, which I gather is what happened in this answer).

@MitchellSpector I meant it as "indicator function of recursively enumerable sets," as Anders says, and I interpreted "some recursively enumerable functions aren't even computable" to be pointing out the basic fact that not every recursively enumerable set is decidable, which made me see my credulity.

@KyleMiller That wasn't meant as a criticism, just as a comment on, or clarification of, what Anders wrote.  The interesting thing is that, even though, as you say, not every r.e. set is decidable, it's nevertheless true that every r.e. function is decidable (where I'm following customary conventions in recursion theory and related areas of mathematics: "function" means "total function", and the function $f$ is identified with the set ${\langle x,y\rangle \mid f(x)=y}$).

JavaScript (Babel Node), 96 86 69 62 bytes
x=>g=([a,b,c])=>c?((v=>{for(;v-->0;)g(b)})(g(a)),g(c)):x[a]+=b

Try it online!
This is implementing a variation on LOOP.  A program is recursively defined to be an array of programs or a BigInt.  A program p is run with input x (a list of BigInts) by passing x and p as curried arguments (f(x)(p) with f the above function).  The program is interpreted as follows:

[i, n] adds n to x[i], returning the sum.
[p, q, r] with c = max(0, evaluate(p)), evaluates q c times then returns the result of evaluating r.

The interpreter expects that every x[i] used is initialized to some BigInt.
For example, the following is a program that returns the product of x[2] and x[3], assuming x[0] is set to 1 and x[1] starts with any non-negative number.
[[0, 0],      // loop x[0] times:
 [[0, 0],     //   loop x[0] times:
  [[1, 0],    //     loop x[1] times:
   [1, -1],   //       x[1] += -1
   [0, 0]],   //     x[0] += 0
  [[2, 0],    //   loop x[2] times:
   [[3, 0],   //     loop x[3] times:
    [1, 1],   //       x[1] += 1
    [0, 0]],  //     x[0] += 0
   [0, 0]]],  //   x[0] += 0
 [1, 0]]      // x[1] += 0

The last line returns the value of x[1].
Note that, while this version of LOOP allows variables to be negative, there is no way to clear such a value in a general way.

Quick golf: c<=1 -> c<2, c==2 -> c<3, ()=> -> _=>, c-->0 -> c--. Also, I think you can start with f=(x,[c,a,b])=>... and remove all the ...s in f(x,...a) etc.

@Bubbler Thanks! My editor's syntax highlighter was unhappy with argument destructuring, so I didn't test it in TIO.

@Bubbler I can't change c-->0 to c-- because c=x[a] might be negative

79 using curried function.

77

VBS, 74 bytes
execute replace(replace(replace(lcase(inputbox(0)),"w",0),"e","ne"),"d",2)

Take program that looks like:
j=0:for i=0 to InputBox():j=j+i:ext:msgbox(j)

Disallow loops from CreateObject, Do, (w)End, eval, execute, step, date, now, timer
JavaScript (Node.js), 35 bytes
(67 if no state allowed, 40 for no state strict, if you keep =; still 35 otherwise, still elementary but program is longer without =)
x=>n=>eval(x.replace(/[^!-=n]/g,0))
x=>n=>eval('for(i in this)delete this[i];'+x.replace(/[^!-=n]/g,0))
x=>n=>eval(x.replace(/[^!-=n]/g,'var '))

Try it online!
Even not reaching Bitwise operation is powerful
JavaScript, 43 bytes
n=>g=([a,b,c])=>c?g(b)/g(c)-g(a)<<g(c):a||n

Why?
0   = 1 / 1 - 1 << 1
-x  = (x / 1 - 0 << 1) / -1 - 0 << -1
x+y = (-x / 1 - y << 1) / -1 - 0 << -1
x/y = -(0 / -y - (x / y - 0 << y) << -y) // If y>0
2^x = 2 / 1 - 1 << x
x>=0 = (1<<x)<<-x
[Convert To Positive]: 2^x + 2^x + 2^x + 2^(-1-x) + 1

I think you need to explain why this can express every polynomial-time function.

@Bubbler I think you can just For for $k$ layers for $n^k$ time, and IF is easily expressed with FOR

I don't know VBS, so take this with a grain of salt, but: According to OP, your interpreter has to validate the program.  Will this interpreter print an error message if the program uses any of the disallowed constructs (CreateObject, Do, etc.)?

@MitchellSpector I’m also not familiar enough with VBScript to be sure whether this is both sufficiently powerful and sufficiently restricted (and I am regretting not having disallowed eval builtins to avoid having the ability to answer these questions depend so crucially on deep familiarity with the host language). But there’s no requirement for an error message in particular, as long as something happens that doesn’t break the other requirements.

@AndersKaseorg  I tend to agree that disallowing eval and variants would have been the way to go, but then people would have complained about that on the grounds that it's not objectively clear exactly which built-ins were being banned.  https://codegolf.meta.stackexchange.com/questions/13771/is-a-built-in-considered-to-be-so-for-all-challenges-it-can-solve-or-only-the/13775#13775

@AndersKaseorg In this particular case, I suspect (but don't know) that those constructs (CreateObject, etc.) were disallowed because they might make the language Turing-complete.  Otherwise, why ban them?  But again, I don't know VBScript, so this is just common-sense speculation.

@AndersKaseorg Fixed

@AndersKaseorg Month require date as input rather than current

Since your interpreter needs to take a program and an input, how is input handled in your VBScript solution?

And for your JavaScript solution, you’re claiming that every function in PTIME (or ELEMENTARY?) can be written with no loops using only big-integer operations? I’m certainly interested in an explanation for this.

@AndersKaseorg https://www.brand.site.co.il/riddles/200902a.html

Bash, 33 bytes
dc -e"?sl`sed "s/[^l+%^]//g;q"`p"

Try it online!
Effectively the same scheme as @xnor's solution, except implemented in sed & dc, and using a subset of dc for user programs. All characters except [+^%l] are filtered out, and those that remain are evaluated by dc. Those characters are sufficient to perform the operations of addition, modulo, exponentiation(with 0^0 == 1) and to read from a variable 'l', which is written to with the user input before the inputted program is run. Numbers may be constructed using a combination of 0 = (n^n)%(n^n), 1 = 0^0, and the successor function, +0^0. Translated to dc, these would be:
0 = llll^llll^%
1 = llll^llll^%llll^llll^%^
S = llll^llll^%llll^llll^%^+

where S increments the value at the top of the stack. Operations may be arbitrarily nested. The set of characters is sufficient to encode the operations listed above. However, it is incapable of producing looping / recursion (which, in dc, would require executing a macro, which would require one of [x=<>], as well as either a or [] to define it). Similarly to @xnor's solution, the allowable programs are a superset of the class ELEMENTARY, adding the ability to do make arbitrary exponents, rather than just 2^ and ^2.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Bilibili AV/BV Code Conversion
Background
Bilibili is a China-based video sharing platform, similar to Nico Nico Douga in Japan, and Youtube around the world.
Since the establishment, Bilibili had been using the AV code to reference a video. An AV code is a string of 3 or more characters, starting with av and followed by a natural number, like av82054919.
However, since 23 March 2020, Bilibili introduced a new referencing system called the BV code. This time, the code is a string of exactly 12 characters, starting with BV and followed by 10 alphanumerical characters, like BV1XJ41157tQ. Still, users can use both codes to reference a video, and there is a conversion algorithm between the two.
(For your information, the two examples reference the same video)
The algorithm
To convert from AV code to BV code:

Remove the av part of the AV code.
Do a bitwise XOR between the result in step 1 (as a number) and 177451812.
Add 8728348608 to the result in step 2.
Convert the result in step 3 to a 6-digit base-58 number with digits fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF in place of 0, 1, ..., 57 respectively. Here, 0, I, O, l are omitted to eliminate ambiguity. Assume the result is abcdef.
The BV code is then BV1db4a1c7ef.

To convert from BV code to AV code:

Remove the 1st to 3rd, the 6th, the 8th and the 10th characters. Assume the result is abcdef.
Rearrange the result in step 1 to cbdaef.
Treat the result in step 2 as a base-58 number with digits fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF in place of 0, 1, ..., 57 respectively. Convert this base-58 number into decimal.
Subtract 8728348608 from the result in step 3.
Do a bitwise XOR between the result in step 4 and 177451812.
The AV code is then av followed by the result in step 5.

Example
To convert av82054919 to BV code:

Removing av from the code results in 82054919.
\$82054919\text{ XOR }177451812=242727971\$
\$242727971+8728348608=8971076579\$
\$8971076579_{10} = (13,38,43,6,30,7)_{58}\$ → 1J5XtQ
Substituting: BV1[X][J]4[1]1[5]7[t][Q] → BV1XJ41157tQ

To convert BV1XJ41157tQ back to AV code:

Remove the bracketed numbers: [BV1]XJ[4]1[1]5[7]tQ → XJ15tQ
Rearranging the characters results in 1J5XtQ.
1J5XtQ → \$(13,38,43,6,30,7)_{58} = 8971076579_{10}\$
\$8971076579-8728348608=242727971\$
\$242727971\text{ XOR }177451812=82054919\$
Prepending av to the result, we have av82054919.

Challenge
Write two independent programs or functions, one receiving the AV code as input and outputting the corresponding BV code, and one receiving the BV code as input and outputting the corresponding AV code. Both the prefixes av and BV are case insensitive, you may choose either upper or lower case to accept or output. Each code should work even without the code from the other.
You may assume that the input for both programs must have a valid format, and the number in its corresponding AV code is between 1 and 2147483647 inclusive.
Test cases
AV code <-> BV code
av82054919 <-> BV1XJ41157tQ
av123456789 <-> BV1yn411L7tG
av1 <-> BV1xx411c7mQ
av2147483647 <-> BV1Fr4k1q7G1

You may check your results through this tool (not developed by me). Click the first button after entering the AV/BV code into the input, then the textbox will show the result.
Winning condition
The total length of the codes of the two programs (measured in bytes) will be your code length, and since this is a code-golf challenge, the submission with shortest code length for each language wins. No standard loopholes.

A useless note: av numbers are not only used to reference videos. There may also be some non-video contents.These includes 3 announcements (1, 1113, 8219) and all posts under Flash game section. Flash game section contains Flash and also Applet, and is no longer available now (due to security reason).

Can we share data between 2 functions, e.g a global string storing the value  "fZodR9XQDSU..."?

Ah, you beat me to it @SurculoseSputum. I was about to ask the same question, since the C answer seems to be doing that, and it would definitely save bytes in every other answer here..

@SurculoseSputum Since basically I'm asking for two independent programs or functions, so I'm not expecting any shared parts. Indeed this exact question was also asked by another user in the sandbox, and that's why I added the word "independent" into the requirements.

I've VTCed this as unclear because it is very unclear how we get from step 4 to 5 in the AV/BV conversion. It took me several readthroughs and some reverse engineering to figure it out.

I have also downvoted as this seems to be a fixed formula with very little logic behind it that leaves next to no room for creative golfing.

I wonder if the permutation of the base-58 character set is totally random or if there's some hidden formula behind it.

2081*2**22+1984==8728348608 and 2081-1984==97==ord('a') for what it's worth.

Python 2, 170 + 150 = 320 bytes
AV to BV, 180 179 173 170 bytes:
lambda s:"BV1{2}{4}4{5}1{3}7{1}{0}".format(*["fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"[((int(s[2:])^177451812)+8728348608)/58**i%58]for i in range(6)])

Try it online!
BV to AV, 165 158 150 bytes:
s=input()
n=0
for i in 6,4,8,3,10,11:n=n*58+"fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF".find(s[i])
print"av"+`n-8728348608^177451812`

Try it online!

Python 3, 518 465 439 422 420 412 406 402 401 bytes
-6 bytes thanks to Surculose Sputum. (I didn't know Python could be made that unreadable!)
-4 bytes thanks to Gavin S. Yancey.
-1 yet another byte gone thanks to Surculose Sputum
Encode:
def s(x):
 b,a=(int(x[2:])^177451812)+8728348608,''
 while b:a+='fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[b%58];b//=58
 return f'BV1{a[2::2]}4{a[5]}1{a[3]}7{a[1::-1]}'

Decode:
def z(i):
 i=i[3:5]+i[6:9:2]+i[10:];a,q,m=i[2]+i[1]+i[3]+i[0]+i[4:],0,1
 for c in a[::-1]:q,m=q+m*'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.index(c),m*58
 return'av'+str((q-8728348608)^177451812)

Try it online!
A fairly simple solution comprised of parts of this and this. Can probably be golfed down a lot, when I get the time. I think it is golfed down to a good-enough level now. And now it works

The first function doesn't seem to work? Maybe you introduced a bug or two while golfing it. For example, I think the 5th line needs to be b//=58. Even with that, it doesn't output the values I expect from the test cases. Tip: Put some print calls in the Footer to demonstrate the code.

@SurculoseSputum (and Neil) Many thanks

You could save 5 bytes on your encode by using an f-string: return f'BV1{a[2]+a[4]}4{a[5]}1{a[3]}7{a[1::-1]}'

And another 1 by replacing a[2]+a[4] with a[2:5:2]

@GavinS.Yancey Thanks!

a[2:5:2] can be just a[2::2], saving 1 byte.

In the second function i[1]+i[3] could be i[1:4:2], saving one byte

05AB1E, 192 164 163 (81+82) bytes
AV to BV - 96 82 81 bytes:
þ•A³ú[•^•2G&©I•+žL¨…lIOм{œ•F
mʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•èÅвA"BV1db4a1c7ef"r‡

Try it online or verify all test cases.
BV to AV - 96 82 bytes:
•1ïÓî•S£ιθSƵª.IžL¨…lIOм{œ•F
mʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•èÅβ•2G&©I•-•A³ú[•^„avì

Try it online or verify all test cases.
NOTE: The TIO's use S with .I (convert to character-list and \$n^{th}\$ permutation builtin) instead of œ with è (get all permutations and index into the list), since generating all permutations is of course way too slow.
Explanation:
AV to BV:
þ                     # Only leave digits of the (implicit) input (to remove "av")
 •A³ú[•               # Push compressed integer 177451812
       ^              # Bitwise-XOR the two integers together
        •2G&©I•       # Push compressed integer 8728348608
               +      # Add the two integers together
žL                    # Push builtin string "zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA9876543210"
  ¨                   # Remove the last character (the "0")
   …lIO               # Push string "lIO"
       м              # Remove those three as well
        {             # Sort the remaining characters in the string
         œ            # Get a list of all permutations of this string
•F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•
                      # Push compressed integer 1563341720558629316384554749509959660779122984425616460522557465911652079492533
 è                    # Index it into the list of permutations:
                      #  "fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"
  Åв                  # Convert the integer to this custom base
    A                 # Push the lowercase alphabet
     "BV1db4a1c7ef"   # Push string "BV1db4a1c7ef"
                   r  # Reverse the three values on the stack
                    ‡ # Transliterate the lowercase alphabet to the base-converted
                      # characters in "BV1db4a1c7ef"
                      # (after which the result is output implicitly)

BV to AV:
•1ïÓî•                # Push compressed integer 32111112
      S               # Convert it to a list of digits: [3,2,1,1,1,1,1,2]
       £              # Split the (implicit) input-string into parts of that size
        ι             # Uninterleave it
         θ            # Only keep the last result
          S           # And convert it to a flattened list of characters
           Ƶª         # Push compressed integer 270
             .I       # And take the 270th 0-based permutation
žL¨…lIOм{œ•F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•è
                      # Same as in the AB to BV conversion above,
 Åβ                   # but the other way around (convert from the custom base to integer)
•2G&©I•-              # Subtract 8728348608
        •A³ú[•^       # Bitwise-XOR it with 177451812
               „avì   # Prepend "av"
                      # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •A³ú[• is 177451812; •2G&©I• is 8728348608; •F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ• is 1563341720558629316384554749509959660779122984425616460522557465911652079492533; •1ïÓî• is 32111112; and Ƶª is 270.
The 1563341720558629316384554749509959660779122984425616460522557465911652079492533 is generated by this Jelly builtin (minus 1, since Jelly uses 1-based indexing and 05AB1E uses 0-based indexing).

This is the closest answer to my bounty request, since it at least uses the fact that the string is a permutation of a subset of the alphanumerics.

C (gcc), 191 + 181 = 372 bytes
Saved 4 5 8 15 bytes thanks to ceilingcat!!!
AV to BV
C (gcc), 224 \$\cdots\$ 198 191 bytes
r[]=L"BV1__4_1_7";e(a,w)long a,w;{w=(strtol(a+2,0,10)^177451812)+8728348608;for(a=6;a--;w/=58)r["6483:;"[a]-48]="fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"[w%58];wprintf(r);}

Try it online!
BV to AV
C (gcc), 224 \$\cdots\$ 186 181 bytes
char*d="fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF",b;long w;c(char*s){for(w=b=0;b<6;w+=index(d,s["6483:;"[b++]-48])-d)w*=58;printf("av%ld",w-8728348608^177451812);}

Try it online!

Charcoal, 208 bytes
AV code to BV code, 117 bytes:
≔⍘"0|7mγη≔Ｉ✂θ²χ¹θ≔⍘⁺⁻｜θη＆θη⍘!,/>#iγ”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”θ≔⁺×f⁻⁶Ｌθθθ⭆BV1db4a1c7ef⎇№βι§θ⌕βιι

Try it online! Link is to verbose version of code. Explanation:
≔⍘"0|7mγη

Get the constant 177451812 into a variable as we need it twice because we don't have a bitwise XOR builtin.
≔Ｉ✂θ²χ¹θ

Extract the value in the AV code as a number.
≔⍘⁺⁻｜θη＆θη⍘!,/>#iγ”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”θ

Subtract the bitwise AND from the bitwise OR giving the bitwise XOR, add the offset, then perform custom base conversion using a compressed version of the given string.
≔⁺×f⁻⁶Ｌθθθ

Pad the string to 6 characters.
⭆BV1db4a1c7ef⎇№βι§θ⌕βιι

Substitute the characters in the appropriate positions in the BV code.
BV code to AV code: 91 bytes:
≔⍘"0|7mγη≔⁻⍘⭆684921§θ±Ｉι”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”⍘!,/>#iγθavＩ⁻｜θη＆θη

Try it online! Link is to verbose version of code. Explanation:
≔⍘"0|7mγη

Get the constant 177451812 into a variable again.
≔⁻⍘⭆684921§θ±Ｉι”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”⍘!,/>#iγθ

Extract the characters from the appropriate positions of the BV code, perform custom base conversion, and subtract the offset.
avＩ⁻｜θη＆θη

Print the bitwise XOR prefixed by av.

JavaScript (Node.js), 322 bytes
f=(s,[a,b,c,d,e,f]=(g=n=>n?g(n/58|0)+'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[n%58]:'')((s.slice(2)^177451812)+8728348608))=>'BV1'+d+b+4+a+1+c+7+e+f
F=s=>'av'+([...'315078'].map(n=>'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.search(s[2-~n])).reduce((x,y)=>x*58+y)-8728348608^177451812)

Try it online!
A simple and stupid solution. Not so creative. But it at least works.

I don't know how easy it is to get into TIO, but can you use btoa`\x7d\x9a\x1dG\xd5\xd0\x0d\x25\x26\xdb\x5c\x82\x92\xbe\xb3\x06\xa8\xafy\x86\xa1\xf1\xbbx\xc6\xc5\xa9\x1erD\xee2\xf9Tm\xe0\xb8\xc4\xca4\xf00p`  in any useful way?

@DomHastings fwiw i think most things are fine to get into TIO, the only exception being nul bytes because textareas don't support that

JavaScript (Node.js), 295 bytes
F=t=>'bv1BD4E1C7A9'.replace(/[9-F]/g,c=>'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[((t.slice(2)^177451812)+8728348608)/58**('0x'+c-9)%58|0])
G=s=>'av'+([7,5,9,4,11,12].map(n=>x=x*58+'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.search(s[n])|0,x=16717449)|x^177451812)

Try it online!
Thank Arnauld for -7 bytes

perl -pl (+ bc), 186 + 189 = 375 182 + 187 = 369 bytes
AV to BV
s/^..//;@_=(split//,fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF)[`echo "obase=58;@{[($_^177451812)+8728348608]}"|bc`=~/\d+/g];$_="BV1$_[3]$_[1]4$_[0]1$_[2]7$_[4]$_[5]"

Try it online!
This uses bc to do the decimal to base-58 conversion.
BV to AV
$n=$x=0;%_=map{$_=>$x++}split//,fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF;@y=@_{/1(.)(.)4(.)1(.)7(.)(.)/};$n=58*$n+$_ for@y[2,1,3,0,4,5];$_=av.(($n-8728348608)^177451812)

Try it online!
If you have only 1 line of input, the first 8 bytes can be removed.
Update: Removed 4 + 2 = 6 bytes, because you don't need to quote the strings.

Prolog, 725 bytes
:-use_module(library(clpz)).
:-use_module(library(lists)).
v(A,B):-var(A),var(B).
d(N,D):-v(N,D),!.
d(N,D):-nth0(N,"0123456789",D).
e(N,D):-v(N,D),!.
e(N,D):-nth0(N,"fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF",D).
b(0,_,[0]).
b(1,_,[1]).
b(A,B,C):-A#>1,E#>=0,L#=E+1,(nonvar(C),length(C,L);nonvar(A)),A#<B^(E+1),A#>=B^E,labeling([down],[E]),length(C,L),reverse(C,F),c(A,B,F).
c(0,_,[]).
c(A,B,[C|D]):-A#>0,C#>=0,C#=<B,E#>=0,C#=A mod B,E#=A//B,c(E,B,D).
a([a,v|A],['B','V','1',E,C,'4',B,'1',D,'7',F,G]):-H=[B,C,D,E,F,G],I=177451812,J=8728348608,K#>=0,L#>=0,K#=L xor I+J,L#=(K-J)xor I,O in 1..9,indomain(O),length(A,O),maplist(d,M,A),maplist(e,N,H),b(L,10,M),b(K,58,N),label([L,K]),maplist(d,M,A),maplist(e,N,H).

Clear version:
:- use_module(library(clpz)).
:- use_module(library(lists)).

v(A, B) :- var(A), var(B).

% Base 10.
d(N, D) :- v(N, D), !. % Keep variable.
d(N, D) :-
    nth0(N, "0123456789", D).

% Base 58.
e(N, D) :- v(N, D), !. % Keep variable.
e(N, D) :-
    nth0(N, "fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF", D).

% Base conversion. Base B, Number A, Array C.
b(0, _, [0]).
b(1, _, [1]).
b(A, B, C) :-
    A #> 1,
    nonvar(B),
    E #>= 0,
    L #= E + 1,
    (   nonvar(C), length(C, L)
    ;   nonvar(A)
    ),
    A #< B ^ (E + 1),
    A #>= B ^ E,
    labeling([down], [E]),
    length(C, L),
    reverse(C, F),
    c(A, B, F).

% Required for b.
c(0, _, []).
c(A, B, [C|D]) :-
    A #> 0,
    C #>= 0,
    C #=< B,
    E #>= 0,
    C #= A mod B,
    E #= A // B,
    c(E, B, D).

% Bidirectional decoder.
a([a, v|A], ['B', 'V', '1', E, C, '4', B, '1', D, '7', F, G]) :-
    H = [B, C, D, E, F, G],
    I = 177451812,
    J = 8728348608,
    K #>= 0,
    L #>= 0,
    K #= L xor I + J,
    L #= (K - J) xor I,
    O in 1..9,
    indomain(O),
    length(A, O),
    maplist(d, M, A),
    maplist(e, N, H),
    b(L, 10, M),
    b(K, 58, N),
    label([L, K]),
    maplist(d, M, A),
    maplist(e, N, H).


text:
SELECT ALL FROM SelectQL WHERE (answer="short" OR NOT length=10000)
I've invented an SQL-like language. Let's call it SelectQL. You can't INSERT anything, you can only SELECT, and I don't have the time for an interpreter. How about you help?
The Challenge
Write a full program or a function that takes in a database of tables and a valid SelectQL SELECT string, interprets the string, and outputs the resulting SELECTion.
SELECT Specification
The SELECT SelectQL statement is as follows (optional portions are in curly brackets):
SELECT [column] FROM [table] {WHERE ( [condition] {[AND/OR] [condition] ... } ) }

[column] can be ALL for selecting all columns, or a valid column name in the [table].
[table] is the name of a table.
The WHERE clause is optional. A WHERE clause is followed by a list of [condition] separated by any of AND or OR, surrounded by parentheses ().
A [condition] is a key-value pair separated by an equals sign =.
[condition] can be preceded with NOT to select the complement of the condition.
Operator Precedence: NOT has higher precedence than AND and OR. AND and OR is executed left to right.
Conditions involving arrays/lists ({980, "abc"} in data below) will look for the existence of a requested value in the array, and return the whole array if true.
key must be a column in [table].
SelectQL query strings are case insensitive.

Table Format
Your program should take in an SelectQL  database (array of arrays, list of lists, delimited string, JSON object, etc) in the following format:
[
    [table name, (column names), [(row), (row), ...]],
    [table name, (column names), [(row), (row), ...]]
]

table name is the name of the table.
[column names] is a list of unique strings which are column names. These are the keys in [condition].
Each column's values all must have the same type.
[row] is a list-like of values. Each row must be the same length as [column names].
There can be no [row]s.
Elements in [row] cannot be empty. Empty strings or arrays are not considered empty.

Types
There are three types in SelectQL: number, string, array.
Numbers are at least 1 digit in 0-9, with an optional decimal point with at least 1 digit.
Strings are double-quote-delimited sequences of characters. Empty strings are possible ("").
Arrays are curly-bracket-delimited comma-separated sequences of numbers, strings, or arrays. Arrays can be heterogeneous. Empty arrays are possible ({}).
Input

A valid SelectQL database, and
A valid SelectQL SELECT query. It will always SELECT a valid table in the database.

Output

The result of the query. The result must have the columns as well as the resulting rows.

Examples
The examples will use the following database:
[
    [data, (d1, d2, 3, ~!@#), [(123, "", {980, "abc"}, "false"), (456, "this isn't empty!", {{},{}}, "-123.4444"), (1, "2", {3, 4}, "five")]],
    [no, (yes, a, 1.5, what), []]
]

Format:
string --> result
-----------------
"SELECT ALL FROM data"
        --> [(d1, D2, 3, ~!@#), [(123, "", {980, "aBc"}, "false"), (456, "this isn't empty!", {{},{}}, "-123.4444"), (1, "2", {3, 4}, "five")]]

"SELECT D1 FROM DATA"
        --> [(d1), [(123), (456), (1)]]

"SELECT d1, 3 FROM data"
        --> [(d1, 3), [(123, {980, "aBc"}), (456, {{},{}}), (1, {3,4})]]

"SELECT ALL FROM DATA WHERE (NOT d1=123)"
        --> [(d1, D2, 3, ~!@#), [(456, "this isn't empty!", {{},{}}, "-123.4444"), (1, "2", [3, 4], "five")]]

"SELECT all FROM data WHERE (d1=123)"
        --> [(d1, D2, 3, ~!@#), [(123, "", [980, "aBc"], "false")]

"SELECT ~!@# FROM DATA WHERE (3={} OR d2="")"
        --> [(~!@#), [("false"), ("-123.4444")]

"SELECT all FROM DATA WHERE (d1=2)"
        --> [(d1, d2, 3, ~!@#), []]

"select all from no"
        --> [(yes, a, 1.5, what), []]

"select 3 from data where (3=980)"
        --> [(3),[[{980, "aBc"}]]

Additional Rules/Clarifications

Standard loopholes are forbidden.
Input and output can be in any reasonable format.
Please explain your answers.
This is code-golf, so the program with the smallest number of bytes wins!

Sandbox Link

May AND and OR be mixed together? If so, what is their precedence?

I guess column1 = column2 comparisons are not supported by the language.

Left to right, so A=1 AND B=2 OR C=3 AND D=4 is ((A==1 and B==2) or C==3) and D==4

@manatwork no, not supported

Can we assume there won't be any spaces between the column = value checks?

@KevinCruijssen No spaces.

What does a row like [123, "", [980, "abc"], "false"], mean, in particular, the third value. How does that work with the = operator?

When you write ''key must be a column in [table]'', what is key? It's the only time you mention key. Did you mean column?

@Abigail it's an array/list/etc and queries in WHERE will look for the existence of an element equal to the requested value, and return the array. Using the data database in the post, select 3 from  data where (3=980) will return [[3],[[[980, "aBc"]]]

Python 3.8 (pre-release), 473 bytes
from re import*
def s(d,q):
 o,f,c=search(r' (?:all|(.*?)) from (\S+)(?:.*?\((.*)\))?',q,I).groups()
 for x,l,r in d:
  u=str.lower;h=bool;m=o and o.split(', ')or l;y=[]
  for g in r:
   p=0;_,*t=split('(?: (?:(and)|or) |^)(not )?(.*?)=',c or'',0,I)
   while t:
    a,n,k,v,*t=t
    p=h(a)&p&(b:=h(n)^any(i==u(k)and(j==eval(v)or list==type(j)and eval(v)in j)for i,j in zip(l,g)))|p|b
   if 1-h(c)|p:y+=[j for i,j in zip(l,g)for z in m if i==u(z)],
  if u(f)==x:print([m,y])

Try it online!
This uses @hyper-neutrino's style of input/output, but is otherwise a completely different implementation.
-5 bytes thanks to @cairdcoinheringaahing.

Assuming a global variable is not allowed.

I see. Updated as instructed. Thanks.

-5 bytes

@cairdcoinheringaahing Ah, did not realize that tuple assignment is more wasteful than semicolon-separated simple statements. The redundant space before the star too. Thanks!

Python 3, 682 bytes
from regex import*
s=lambda x:str==type(x)and x.lower()or list==type(x)and[*map(s,x)]or x
V=eval
E=lambda x:str(V(x.group()))
def f(d,q):
	c,t,w=match("select (.+) from (.+?)(?: where \((.+)\))?$",s(q)).groups()
	K=[[C for C in map(s,y)if{*c.split(", ")}&{"all",C}]for x,y,z in d if s(x)==t][0];r=[]
	for R in{s(x):[{s(k):l for k,l in zip(y,r)}for r in z]for x,y,z in d}[t]:
		if w:
			v=sub("not \w+",E,sub(r'(\S+)=(\[((?2)(, *(?2))*)?\]|"[^"]*"|\d+)',lambda x:str(e(s(R[x.group(1)]),s(V(x.group(2))))),w))
			while len(v)>5:v=sub("\w+ \w+ \w+",E,v,1)
			if~-V(v):continue
		r+=R,
	print([K,[[q[x]for x in K]for q in r]])
e=lambda x,y:x==y or list==type(x)and any(e(v,y)for v in x)

Try it online!
-5 bytes thanks to Razetime
-18 bytes thanks to caird coinheringaahing
this was painful
This uses [] for arrays because that's Python's list representation. Please let me know if this is invalid. The DB is just taken in the representation given in the question as a native Python object.

c is only used once so you can inline c.split

[] is perfectly fine for arrays

-18 bytes

Python 3, 583 bytes:
import re, operator as o
def f(a,q):
 [[c,b]],z=[(c,d)for t,c,d in a if t==(r:=re.findall(' (.+) FROM (\w+)',q)[0])[1]],lambda n,m,w:[o.pos,o.not_][w](n in m if type(m)==set else n==m)
 d=[dict(zip(c,i))for i in b]
 p=lambda e,i:(eval((v:=e.pop().split('='))[-1]),i[re.sub('NOT\s','',v[0])],v[0][:3]=='NOT')
 return (g:=[c,r[0].split(', ')][r[0]!='ALL']),[[i[j]for j in g]for i in d if(y:=lambda e,u:True if not e else(z(*p(e,i))if not e[:-1]or not u else[o.and_,o.or_][u.pop()=='OR'](z(*p(e,i)),y(e,u))))(re.findall('(?:(?:NOT\s)*\w+\=(?:\{.*?\}|".*"|\w+))+', q),re.findall('AND|OR',q))]

welcome to codegolf! Nice first answer! But can you add a TIO link that run the code? this way others can help you golf down more bytes

here’s a TIO link for your code


text:
List of programming languages that can run code at runtime
What all languages have a construct similar to python's eval, so you can write code during runtime and run it?
A list would be helpful for certain programming challenges - ones where it is obvious an eval is either necessary or highly efficient.

I'm not sure on the answer format, would a community wiki answer be better? Or one language per answer?

You can cross C++ off the list! T_T

A few I recall:

Lua: loadstring("2 + 2")
*Script (Coffee, Java, Type, Action): eval("2 + 2")
Erlang / Elixir: Code.eval_string("a + b", [a: 2, b: 2], file: __ENV__.file, line: __ENV__.line)
J: ". '2 + 2' (eval it right away) or 3 : '2 + 2' (define a function; (3 : '2 + 2') 0 runs it)
Ruby: eval "2 + 2"
Perl: eval "2 + 2"
Bash: a="ls | wc -l", eval $a
PHP: eval("2 + 2")
Lisp, obviously: (setq test'(+ 2 2)) and (eval test)
Python: eval('2 + 2')
ColdFusion: <cfset x = "int(2+2)"> and <cfset y = Evaluate(x)>
FORTH: S" 2 2 + ." eval (note: it depends on the implementation; most use either EVALUATE or eval)
VBScript, VBA: Execute('2 + 2') (note: for VBA as far as I recall, it's eval)
Smalltalk: Compiler evaluate:'2 + 2'
APL: The ⍎ primitive executes a character vector that contains a valid APL expression: ⍎ '2×3' or ⍎ 'S←A String'. The former will execute the mathematical expression and return 6; the latter will create a variable S in the APL workspace, and assign it the value A String
PowerShell: invoke-expression '2 + 2'
R: eval(parse(text = "2 + 2"))
Io: doString("2 + 2")
Burlesque: "2 2.+"pe

Other languages:

Java: see ScriptEngine functionality.
C, C++: they can execute shellcode
D: via mixins, int a = 0; and then mixin("a = 2 + 2;"); (note: the string must be constant and known at the compile time)

APL, using the ⍎ primitive - if S is a character vector containing a valid APL expression, ⍎S will execute it.

R: eval(parse(text = "2 + 2"))
There is a reason it's not great for golfing

@AshleyBaldry well, it's not too bad; that can be golfed to eval(parse(t="2 + 2"))

"2 2+".V (regular eval) or "2+2".E (python-eval) could be added for 05AB1E and “2 2+”V or “2+2”V for Jelly (V uses either regular or Python eval automatically). Maybe this would be better suited as a cw answer so everyone could add to it (and you could maybe also add TIOs to verify each eval). But +1 for listing all of these yourself already. :)

Bytecode could technically work too. You can dynamically load more bytecode while running.

C certainly have the ability to run code without executing shell code -- a myriad of security holes are based on buffer overflows forcing the executable to run injected code. Nothing stops the programmer to do the same.

Any language which is self modifying can 'run code at runtime'. Interpreters usually can do this easily, examples being many assemblers, Befunge and other fungoids, but also many shells. And don't forget The Story of Mel for a brilliant use of self modifying code.

T-SQL has EXEC.

SNOBOL4 has EVAL(s).

feel free to add them yourselves if you find something, it gets some rep points

BASIC has DEF FN F(X)=X+X

Wait, is C golfing by including parts written in raw shellcode a reasonable strategy?

maybe; would need to investigate that - code can contain unprintable characters, or you may construct unprintable shellcode

But then jumping into that shellcode might be a problem due to type issues (unless it is the entry point)...

JavaScript: eval(str)

^- it's already there.

@Bubbler gcc lets you use goto


text:
Resource for generating shortest regex given a list of strings
I'm looking for a program such that, given a finite list of strings, can find short regexes to match exactly all of them and nothing else.
Since there are multiple languages that express regexes differently, there can correspondingly be multiple regex generators. Each answer must discuss regex generation in one langauge only (or a family of languages for which there is a direct correspondence between regexes in each of them).

@Arnauld Yeah, I thought the "exactly" made it clear enough. Edited.

Do you mean like matching 'dome' and 'home' with the regex (h|d)ome?

@Krish yes, that's what I mean

Another useful feature of such a tool would be to generate a regex that matches all strings in a list A but not any of the strings in a list B, with undefined behavior for any other input. (This is what I would have needed to optimize this handcrafted answer.)

@Arnauld that's more specific though. An answer to mine can give you two regexes and then do A and not B, ofcourse not optimal though

@Arnauld Writing a regexp which matches all strings in a list, and no other strings, is trivial. For instance, in Perl, you can write my $pat = '^(' . join ("|"  => map {quotemeta $_} @list_of_strings) . '$)'; This would match all strings from the list, and no others. It's not the shortest though. Shortest regexp to match all strings in a list, and no others, sounds doable. Shortest regexp which matches all strings in a list, no strings in another, and don't care for all other strings sounds much harder.

How do the strings you want to match look like? ASCII? Unicode, and if so, in which format? If Unicode, should the single character "LATIN SMALL LETTER A WITH ACUTE" match the two character string "LATIN SMALL LETTER A; COMBINING ACUTE ACCENT"? That is, do you match on character, or on grapheme? If not on grapheme, should you match on a normal form, or just as is?

@Abigail Depends on what the respective language natively supports as stdin, which is usually ASCII

@ghosts_in_the_code I'd say most languages treat file handles (any kind, including STDIN) as a stream of bytes, and it's up to the program to decide how those bytes should be interpreted.

@Abigail okay not stdin then, I mean does the language natively support unicode strings? Does it's native regex matching functionality work on these unicode strings? If no, then stick to ascii. Also it's a technicality that isn't really relevant to the question imo.

@Abigail I'm not asking someone to implement a regex functionality for unicode, only try generating regexes in langauge that already natively support regexes. So the language must support unicode matching of regexes for unicode to be part of the discussion

I don't think this challenge is as interesting as it seems at first.  Take the words ['roamer','homer','boomer'].  The shortest such regex is (roa|ho|boo)mer.  But as soon as you make boomer plural, the shortest regex becomes ((roa|ho)mer)|boomers.  With a realistic list of more less similar words, it will quickly devolve into a mere pipe-separated list of the provided words.

@GirkovArpa Firstly this is not a challenge, it's a meta question to help solve all the questions that benefit from regexes. The questions that do, typically use words with lots of overlap so that good regexes can exist

Okay, thanks for the clarification.  I'm new and did not know there were non-challenge questions here.

For arbitrary input, how can you prove output is the shortest possible without bruteforcing every shorter regex as well?

@golf69 I'm sure there are proof techniques for it but I'm not necessarily looking for only those regexes that are provably shortest (I'll edit the q thanks for it). And yeah my answer is basically looking for a "smart" brute force approach only

It seems to be very hard or impossible even without golfing...

@VictorVosMottorthanksMonica without golfing, trivial solution is to connect all the string with "and"

@ghosts_in_the_code You said shortest regexes.

@VictorVosMottorthanksMonica so that's what golfing is. Idk what you meant without golfing

@ghosts_in_the_code to write code implementing it without reducing it(code).

@VictorVosMottorthanksMonica oh yeah the regex generator doesn't have to be golfed

Seems NP-hard.

The Machine Learning Lab at the University of Trieste, Italy, wrote a web app to solve this exact problem, available at: Automatic Generation of Regular Expressions from Examples based on "genetic programming" and published a paper about it. Based on the fact that it had to come from the Machine Learning Lab of a university in Italy, and was worth publishing a paper about, it is probably a pretty hard problem to solve. Doesn't sound like the type of question for Code Golf SE, but I'm new here, so I wouldn't be the expert on that.

Welcome to the site. That's a cool approach to regex generation. Note, though, that the app isn't guaranteed to find the shortest possible regex. From the FAQ: '3. The generated regexes look unoptimized. Why? There are some optimization which could make a given regex appear better, e.g., [\d\d\.\d] → [\d\.]. Currently, our prototype does not apply any of these optimizations.' Nor will the generated regex match only the given strings and nothing else. You are right - this is a hard problem.

I didn't look into it, but the description of the website I linked does include "old version", so maybe there is a newer version which does apply the optimizations? I seem to remember the website looking different the first time I saw it than this time around, so maybe I really did link an old one...

I believe I linked to the "Regex Generator" page, here is the "Regex Generator++" page: http://regex.inginf.units.it/ . I updated the post. I wonder if the ++ version does perform the optimizations...

I believe that the ++ version does perform the optimizations. At least, in the regex golf section - which looks more similair in its UI to the ++ version - it has a stage when it is figuring out the Regex where it says "Optimizing..."

I would approach this problem by searching for common subsequences in each pair of strings in the list, and then building regular expressions that include those subsequences. This would be somewhat like the Re-Pair algorithm, but it would build a grammar from a set of strings instead of one string.
For instance, these strings:
["red wolf", "red fox", "gray wolf", "gray fox"]
could be combined into two regular expressions:
"red (wolf|fox)", "gray (wolf|fox)"
which can be combined into one regular expression:
"(red|gray) (wolf|fox)"
But this problem is probably NP-complete, since it is similar to the smallest grammar problem.

Welcome to Code Golf! This site is for competitive challenges, not for asking and answering actual questions.

@RadvylfPrograms Yes, I think this question should have been posted on Computer Science Stack Exchange instead of Code Golf.

Ohhhh hang on yeah you're right. Didn't notice this is tagged with [tag:tips], this would definitely be better somewhere else.


text:
Is there a language that supports Turing machines?
Is there a programming language that supports single tape Turing machines specified in some format?
I am aware multiple formats for expressing them exist, but is there a standard one using which an acceptable answer can be published on this site?
If it doesn't exist can somebody create one? Golfing Turing machines has academic relevance too.

This is one turing machine sim that you can at least link too, TIO has one too. Unfortunately, there aren't any golfy ones I know of. But your question is not very clear.

@Wezl Any way I can submit Turing machines as answers and have them satisfy the requirements of the site, is what I meant to say

@ghosts_in_the_code I have seen answers in pure turing machine code. Example: https://codegolf.stackexchange.com/a/200380/95627

@nph oo so that simulator is acceptable? By the way the spaces seem redundant and nearly double the total byte count

@ghosts_in_the_code It appears to be acceptable. I think you can leave out the spaces.

I’m voting to close this question because it is off topic for the site.  It should have been asked on or migrated to meta, but it is too late for that now.

It should be acceptable to post answers in pure turing machine code. I have seen people do this before.
Examples:
https://codegolf.stackexchange.com/a/200380/95627
Simple cat program
If anyone knows more about this, you can edit.

I’ve made one.
It’s an interpreter written in Python, so it’s not ideal for anything intensive, but the source format is fairly concise for golfing. It uses Unicode characters as tape symbols.