Albedo
Joined 24 August 2022
languages added
(→Integer Sequence: Ackermann Function added) |
(languages added) |
||
| (7 intermediate revisions by the same user not shown) | |||
Line 1:
{{mylangbegin}}
{{mylang|Piet|
{{mylang|Julia|
{{mylang|Cardinal|Pro}}
{{mylang|DUP|Intermediate}}
{{mylang|FALSE|Intermediate}}
{{mylang|Beeswax|Creator}}
{{mylang|Glee|Beginner}}
{{mylang|Q'Nial|Beginner}}
{{mylangend}}
There aren’t any ways to upload images at the moment, so
==Explanation of shorthand code for Piet examples==
To shrink down the size of larger problems, I invented a shorthand text version for explaining the general program flow in a more compact form:
. + / > = c ~
X - % # @ N
? * ! $ n C
==Ackermann Function==
Line 375 ⟶ 385:
|}
Program flow (see explanation of the shorthand codes at the top of the page), with labels:
l1 l3
↓ ↓
1X2X-nn2X1X@=1X=->!#2X1X@=1X=-
. l2→? >
. 2 !
................X1-X1?#
. X l4↑2←l5
. 1 X
. X 1
. @ X
. = @
. 1 =
. ~ X 3
. N = X
. + - 1
. X 2 X
. 1 X @
. l6→? 1 1
.+X1@X1X2#>@X X
. l7↑ -
...............-X1@X1X3
Explanation with stack for the Ackermann Function(2,0):
(for the meaning of the square brackets, please read below)
[A] [B]
1 1
1 1 1 0 1 1 1 0
2 2 2 2 2 2 1 0 2 2 0 0 0 0 0 1
0 0 0 [2] 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 1 [1]
2 2 2 2 2 [0] 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 1 [1]
1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
———————————————————————————————————————————————————————————————————————————————————————
1X2X - n n 2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # ? 1X - 1X
↑ ↑ ↑
l1 l3 l4
---------------------------------------------------------------------------------------
explanation: correct order m>0? yes n>0? no A(m-1,1)
of m,n
[B] [C]
1 1 1 1
1 1 1 0 1 1 1 0 1 3 3 1 3 3 1
2 2 1 1 1 1 1 0 2 2 1 1 1 1 1 0 2 2 1 1 1 1 1 0 0 0 1 1 [0]
1 1 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 [1]
1 1 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 [0]
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
——————————————————————————————————————————————————————————————————————————————————————————————————————
2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # 2X 1X @ = 3X 1X @ 1X - 3X 1X @ 1X -
↑ ↑ ↑
l1 l3 l5
-------------------------------------------------------------------------------------------------------
correct order m>0? yes n>0? yes A(m-1,A(m,n-1))
of m,n
[D]
1 1 1
1 1 1 0 1 1 1 0 1 1 0
2 2 1 1 1 1 1 0 2 2 0 0 0 0 0 1 2 2 0 0 0 0 0 1
0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 [1] 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 [0] 0 0 1 1 1 1 1 1 1 1
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
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
—————————————————————————————————————————————————————————————————————————————————————————————————————
2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # ? 1X - 1X 2X 1X @ = 1X = - > ! #
↑ ↑ ↑ ↑
l1 l3 l4 l1
-----------------------------------------------------------------------------------------------------
correct order m>0? yes n>0? no A(m-1,1) correct order m>0?
of m,n for inner inner for inner f.
function function
1
1 2 2 1
1 1 1 0 0 0 0 1 1 1 1 0
2 2 0 0 0 0 0 0 0 0 2 2 1 2 2 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 2 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 2 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
———————————————————————————————————————————————————————————————————————————————————
? 2X 1X @ = 1X = - 2X 1X @ > # 2X 1X @ 1X + 2X 1X @ = 1X = - > ! #
↑ ↑ ↑
l2 l7 l1
output 3
—————————————————————————————————————————————————————
1
1 2 2
1 1 1 0 0 0 -1
2 2 -1 -1 -1 -1 -1 -1 0 1
2 2 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1
-1 -1 -1 2 2 2 2 2 2 2 2 2 2 2 2 3
—————————————————————————————————————————————————————
? 2X 1X @ = 1X = - 2X 1X @ > # ? 1X + N ~
↑ ↑
l2 l6
Which leads to the result Ackermann(2,0) = 3
What the program actually does is working through the whole steps of calculating the A(m,n) functions, according to:
A(2,0) = A(1,1) ,A(m,n)= A(m-1,1) if m>0 and n=0
A(1,1) = A(0,A(1,0)) ,A(m,n)= A(m-1,A(m,n-1)) if m>0 and n>0
A(0,A(1,0)) = A(0,A(0,1)) ,A(m,n)= A(m,n-1) if m>1 and n=0, for the inner function
A(0,A(0,1)) = A(0,2) ,A(m,n)= n+1 if m=0, for the inner function
A(0,2) = 3 ,A(m,n)= n+1 if m=0
The coefficients and the results can be found on the stack. See the places marked with square brackets [] and Labels in the program/stack flow above.
At each turn, the upper two values on the stack are flipped, so they are in the proper order for computing inner functions. For highly nested A(...,(A(A(A(...))))) functions the stack can grow to enormous proportions very fast, then computing its way outwards again, from innermost functions outwards. The innermost coefficients are always on top of the stack.
Checks for the appropriate substitute function and branching structures take the largest part of the program.
==Binary Digits==
[[Binary digits#Piet]]
png image download:
Line 613 ⟶ 655:
|-
|}
Example output:
? 3
11
? 13
1101
Program flow (explanation of codes at the top of the page):
Line 676 ⟶ 727:
↑ . .
l4 ....
==Integer Sequence==
[[Integer_sequence#Piet]]
PNG image download:
[Image:https://copy.com/TQuwy3dwBRl7nEOL]
Rendered as wikitable:
{| style="border-collapse: collapse; border-spacing: 0; font-family: courier-new,courier,monospace; font-size: 20px; line-height: 1.2em; padding: 0px"
| style="background-color:#ffc0c0; color:#ffc0c0;" | ww
| style="background-color:#ff0000; color:#ff0000;" | ww
| style="background-color:#c0ffc0; color:#c0ffc0;" | ww
| style="background-color:#ffc0c0; color:#ffc0c0;" | ww
| style="background-color:#ff00ff; color:#ff00ff;" | ww
| style="background-color:#ff00ff; color:#ff00ff;" | ww
| style="background-color:#c000c0; color:#c000c0;" | ww
|-
| style="background-color:#000000; color:#000000;" | ww
| style="background-color:#000000; color:#000000;" | ww
| style="background-color:#0000ff; color:#0000ff;" | ww
| style="background-color:#ff00ff; color:#ff00ff;" | ww
| style="background-color:#ff00ff; color:#ff00ff;" | ww
| style="background-color:#ff00ff; color:#ff00ff;" | ww
| style="background-color:#00c0c0; color:#00c0c0;" | ww
|-
| style="background-color:#000000; color:#000000;" | ww
| style="background-color:#000000; color:#000000;" | ww
| style="background-color:#0000ff; color:#0000ff;" | ww
| style="background-color:#0000ff; color:#0000ff;" | ww
| style="background-color:#00c0c0; color:#00c0c0;" | ww
| style="background-color:#00ffff; color:#00ffff;" | ww
| style="background-color:#0000ff; color:#0000ff;" | ww
|}
(7x3 codels)
Opcodes:
1 PSH NOT DUP OUN 5 PSH
ROL
ADD DUP
PSH 1 OUC ADD
Shorthand:
1 X ! = N 5 X
@ .
+ =
X 1 C +
0 \n 1 \n 2 \n 3 OUTPUT
—————————————————————————————————————————————————————————————————————————————
5 5 5
0 5 5 10 1 1 5 5 10 1 2 5 5 10 1 3 STACK
1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 ...
—————————————————————————————————————————————————————————————————————————————
1X ! = N 5X = + C 1X + @ = N 5X = + C 1X + @ = N 5X = + C 1X + @ = N ...
| \_____/ | | |
| | | | +—————————— Repeating the Loop
| | | |
| | | +———————————— ROL acting as NOP (stack too small), needed to guide the codel chooser
| | |
| | +—————————————— Count up
| |
| +———————————————————————— 10 = ASCII for \n (newline)
|
+————————————————————————————————— !1=0 (Sequence begins at 0)
| |||