Talk:Listack
With the changes in Listack v0.4, I really need to update this page. The code examples still work in Python, but probably not in the Nim version.
Listack v0.3 page
Listack: A symmetric, stackless, stack-based, concatenative language Listack is an experiment in making a symmetric, stackless, stack-based, concatenative language. Listack was inspired by Factor, XY, and Falsish , which is itself a variant of False inspired by fish ><>. The user-defined type system was inspired by Euphoria. Listack is symmetric in that most command words are available in a prefix, infix, and postfix form. The user can choose which forms to use, and can thus mimic Lisp (prefix), Forth (postfix), or use a mix of all three forms in the style of most imperative languages. The prefix and infix forms are created from the base postfix form by meta-programming. (This is a slight variant of Uniform Function Call.) Listack is stackless in that the implementation is very nearly a Turing machine, with a stack for past data, the current command, and then a queue for future commands. Commands are read from the front of the queue, and the data computed by these commands is pushed onto the stack, creating, in effect, an infinite tape. As such, the language is implemented as a simple loop with no recursion and no return stack. Invocations of functions ("words") merely place the function definition on the front of the command queue. Loops are implemented by repeatedly pushing the body of the loop back onto the front of the command queue (which is basically tail-call recursion). There is no call, no return, no goto, no instruction pointer, only adding words to the front of the command queue. Functions are words that contain blocks of other words, which are expanded at the front of the command queue when called. In other words, all functions are inline functions. Concatenative languages, which are normally stack-based, are similar to many functional languages in that function composition is accomplished by typing one command after another. The output from one word is the input to the next word via the data stack, much like the *nix pipe ("|") command. This makes them very close analogues to the lambda calculus. So, concatenative languages seem to highlight the similarities between the Turing machine and lambda calculus theories of computation.
Listack is a pun on List and Stack based programming. It was created by McChuck and implemented in Python 3.10 in January 2023. Listack version 0.4.0 was rewritten in Nim 1.6.12 and uploaded to GitHub on 20 May 2023. Besides being much faster, there are numerous additions and changes. For example, meta-programming was eliminated in favor of using custom global stack variables.
Features Commands are called words in the concatenative tradition. Every instruction is a word, and every word is an instruction. Most Listack words are available in prefix, infix, and postfix variants. By convention, the prefix variant ends with ":" and the postfix begins with ".". Commands are implemented as postfix, with the variants constructed using metaprogramming. After all, the only difference between these commands, other than their tokens, is the order in which the operands appear.
Prefix +: 1 2 Infix 1 + 2 Postfix 1 2 .+
The data types are INT, FLOAT, STR, LIST, BLOCK, BOOL, and WORD Numbers are immutable and pushed onto the stack. Strings are immutable and pushed onto the stack. Strings can be converted into lists and vice-versa. Sequences (lists and blocks) are mutable and pushed onto the stack. There is very little practical difference between a list and a block in the language implementation. As the saying goes, "It's all just data." Lists "[ ]" contain data (which can include words). Blocks "{ }" contain words (which can include data), and serve as lambda function expressions. The traditional concatenative programming term "quotation" is eschewed in favor of "block", as in code block, thus the curly braces. Collections "()" can be substituted for both blocks and lists to enhance readability. Words execute their function definitions. Both local and global variables are available. Local variables A..Z are always available and initialized to "". Global "side" stacks a..z are always available using push_ and pop_. Local variables can be created using "init". Global variables/functions can be created using "def". Local variables place their contents onto the data stack. Global functions place their definition at the front of the command queue. Functions definitions can examined and altered with "get" and "set", and variable contents can be executed with "call". Variables are referenced by name, and act as words. Variable names cannot begin with a number or reserved character. "." can only appear at the beginning of a word. (Floats, of course, contain a period by definition.) ":" can only appear at the end of a word. Variables can be addressed with "get" and "set". @varname is shorthand for "get", while $varname is shorthand for "set" and !varname for "call". Scope is administered manually, and was inspired by fish. Scope is opened by "|>" closed by "<|". "n |>" removes n items from the top of the data stack, creates a local scope, initializes local variables A..Z, sets the values of A..N to the items taken from the stack, creates a new data stack (saving the old one for later use), and pushes the n items onto the new stack. "<|" copies all remaining items on the current stack onto the old stack, then clears and deletes the current data stack and local variable set. Yes, this means there is a stack of stacks. Yes, you can manually save and restore the data stack. The data stack is implemented as a deque (double ended queue). It is reversible and rotatable. Control flow, other than the execution of words one by one, is accomplished with a series of more and more complex functions based on 'choose' and 'exec'. {condition}{true}{false}.choose --> based on the boolean result of "condition", choose deletes either the "false" (if true) or "true" (if false) block (or word). {condition} {do if true} {do if false} .if --> .if is actually implemented as .choose.exec while: {condition} {body} --> "cont" and "break" are available in the body of a while loop. [list of data to act upon] {body of words to execute} .each --> applies body to each element of the data list. [data to act upon] map {words to execute} --> differs from "each" in that the results are collected into a list. n times {words to execute} --> counts down from integer n to 0. The current value of n is stored on side stack t. [{initialize} {incremental change} {exit condition}] {body} .for --> the current counter is stored on side stack f. A rather long list of command words is available. Not every possible function has been implemented, as the language is intended as an experiment and proof of concept. Listack is by no means efficient. It is parsed and interpreted using a couple thousand lines of Python 3.10 code. Meta programming Meta programming is used to create the pre- and infix variants and also to copy and move words around in the control flow words. Meta programming is fully available to the user. [num_past, num_future, "pattern"] _meta_ --> Pop a number of items from the stack and the queue, and apply them using "pattern" to the front of the queue.
- a .. #n applies items from the stack, in order a (lower in stack) to n (top of stack).
- A .. #N applies items from the queue in the same way.
%a expands a sequence.
- B0 takes the first item from the sequence denoted by B. Only one digit can be used, so you can only go 10 items deep into a sequence.
.while is implemented as: [2, 0, "%a {%b begin_while #a #b .while} {nop} .if"] --> "begin_while" is used by cont and break, and evaluates to nop (no operation / pass). while: is implemented as: \ .while _ins_f2 while is implemented as: \ .while _ins_f1 Example programs
- Summation sequence functions
println:"Simple Summation!"
def: "simple_summ"
{dup .print " --> ".print dup
> 0 if
{dup while: {1 .- dup 0 .>}
do {dup roll .+ swap}
drop .println}
else {drop 0 .println}
}
10 simple_summ # 55
10.5 simple_summ # 60.5
0.5 simple_summ # 0.5
0 simple_summ # 0
-5 simple_summ # 0
println:"\nGeneral Summation!"
def: "general_summ" {
dup .print " --> ".print dup
<=>
{dup {1 .+ dup 0 .<} {dup roll .+ swap} .while}
{dup}
{dup {1 .- dup 0 .>} {dup roll .+ swap} .while}
drop .println }
10 general_summ # 55
10.5 general_summ # 60.5
0.5 general_summ # 0.5
0 general_summ # 0
-0.5 general_summ # -0.5
-10 general_summ # -55
-10.5 general_summ # -60.5
println:"\nFast Summation!"
def: "fast_summ" {
dup dup .print " --> ".print
<=> # trinary branch based on sign of number
{1 ./% swap dup roll swap 1 .- .* swap dup 1 .- .* -2 .// swap .-} # negative
{nop} # zero
{1 ./% swap dup roll swap 1 .+ .* swap dup 1 .+ .* 2 .// .+} # positive
.println }
10 fast_summ # 55
10.5 fast_summ # 60.5
0.5 fast_summ # 0.5
0 fast_summ # 0
-0.5 fast_summ # -0.5
-10 fast_summ # -55
-10.5 fast_summ # -60.5
#
# test of string & list conversions, each, for, times, break, cont, range
#
{32.emit} "sp".def
{10.emit} "cr".def
"Let's see if this works." dup
.str>list_word dup {.print sp}.each cr
.rev {.print sp}.each cr
.str>list_char.rev.list>str.println # function composition is just putting one command after another
[{10} {- 1} {< 0}] for* {dup .print ~< 1 iff {", ".print}} print:" Liftoff!" cr
# "~<" is "not less than", same as ">="
# "iff" is "if and only if", no else block
# "for*", like "times*", pushes the current value of the counter onto the stack before executing the code block
3 times {"Beetlejuice! ".print} cr
{[].not} while {println:"This is a silly way do to an iff!" break}
[3 2 1 0] {.len > 0} while {.first* dup .print {> 0} iff {sp cont} println:" 'cont' test complete!"}
1 .. 10 .print "d" .. 'a' .println
# ".." is semantic sugar for infix "range", must have spaces around it to not confuse it with numbers or other words
# output is:
# Let's see if this works.
# works. this if see Let's
# .skrow siht fi ees s'teL
# 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 Liftoff!
# Beetlejuice! Beetlejuice! Beetlejuice!
# This is a silly way do to an iff!
# 3 2 1 0 'cont' test complete!
# [ 1 2 3 4 5 6 7 8 9 10 ] [ d c b a ]
#
# Ackermann intensely recursive function
#
# dip combinator
{swap _ins_f1 .exec} ".dip" .def # a b {some} .dip --> a some b
def: ".ack" { # expects two non-negative integers m, n
over 0 .<= if
{swap drop 1.+} # if m=0, return n += 1
else {dup 0 .<= if
{drop 1 .- 1 .ack} # else if n=0, ack (m-1, 1)
else {{dup 1 .- swap} .dip 1 .- .ack .ack} # else ack(m-1, ack(m, n-1))
# .dip really does make it easier to read, instead of: {over swap 1 .- .ack swap 1 .- swap .ack}
}
}
[[0 0] [0 1] [0 2] [0 3] [0 4] [0 5]] {.delist drop .ack .print sp} .each cr
[[1 0] [1 1] [1 2] [1 3] [1 4] [1 5]] {.delist drop .ack .print sp} .each cr
[[2 0] [2 1] [2 2] [2 3] [2 4] [2 5]] {.delist drop .ack .print sp} .each cr
[[3 0] [3 1] [3 2] [3 3] [3 4] [3 5]] {.delist drop .ack .print sp} .each cr
4 0 .ack .println
# 1 2 3 4 5 6
# 2 3 4 5 6 7
# 3 5 7 9 11 13
# 5 13 29 61 125 253
# 13