robertbendun/stacky

Stack based programming language

stacky

WIP stack-based compiled concatenative programming language.

Currently is developement is postponed, due to other projects (and university) with higher priority.

It's somewhere between B and C programming languages in universe where B was stack based concatenative language.

Features

• Turing completness
• Optional type checking
• Low level OS access ability

Example

hello, world

# hello.stacky
"io" import

"hello, world" puts nl

$ stacky run hello.stacky
hello, world

puts current date

# date.stacky
"io"   import
"time" import

"Date is " puts

now  # returns seconds in Unix time
date # returns year, month, day, hours, minutes
	   putu "-" puts
	2 aputu "-" puts
	2 aputu " " puts
	2 aputu ":" puts
	2 aputu nl

$ stacky run date.stacky
Date is 2021-10-17 23:13

Language reference

Control flow

if ... else ... end

Consumes top of the stack. If value was nonzero, executes if branch, otherwise else branch.

"io" import
10 if "value is 10!" else "value is not 10 :c" end puts nl

while ... do ... end

While condition part (between while and do) is nonzero, executes repeatadly loop part (between do and end).

# puts numbers from 0 to 10
"io" import

0 while dup 11 = ! do
	dup .
	1 +
end

Functions

<name> fun <code> end creates function with given name and code block.

"io" import

say-hello fun "Hi, " puts puts "!\n" puts end

"Mark" say-hello # prints "Hi, Mark!"

Address of functions

&<name> puts <name> address onto stack, for example: &foo

Call operator

call calls function pointed by address on top of the stack.

"Mark" &say-hello call

Standard library

algorithm

• uniform32 - (a b -- n) returns random integer n in range [a, b]

io

• nl - putss newline to stdout
• puts - (pointer --) - prints null terminated string to stdout
• . - (uint --) - puts unsigned integer to stdout with a newline at the end

limits

• Max_Digits10 - (-- uint) - returns maximum number of decimal digits that unsigned integer may have

time

• now - (-- seconds) - returns number of seconds since Unix time

• sleep - (seconds --) - sleeps given number of seconds

• date - (seconds -- year month day hours minutes) - decomposes seconds since Unix time into human readable form

• +minutes - (minutes seconds -- seconds) - adds minutes to seconds

• +hours - (hours seconds -- seconds) - adds hours to seconds

• +days - (days seconds -- seconds) - adds days to seconds

• +weeks - (weekds seconds -- seconds) - adds weeks to seconds

• -minutes - (minutes seconds -- seconds) - subtracts minutes from seconds

• -hours - (hours seconds -- seconds) - subtracts hours from seconds

• -days - (days seconds -- seconds) - subtracts days from seconds

• -weeks - (weekds seconds -- seconds) - subtracts weeks from seconds

posix

Contains definition of constants related to POSIX compatible operating systems.

• SYS_<syscall> - constants holding syscall numbers, like SYS_exit = 60
• stdin, stdout, stderr
• CLOCK_<type> - definition of clocks constants for clock_gettime syscall

Makefile

• make install-nvim - installs Stacky's syntax highlighting for Neovim
• make stacky - makes only compiler
• make test - runs all tests
• make clean - cleans all intermidiate files

Requirements

• NASM
• LD
• GCC with C++ compiler for compiler and stdlib compilation
• Boost Program_Options

For Arch-based users:

pacman -S gcc binutils nasm boost

See also

• Tsoding Porth (main inspiration for starting this project)
• Classic stack based language Forth
• Modern stack based functional language Factor

stacky's Issues

`static` keyword and compile time code execution

The idea is that static would enable compile time code execution in Stacky. This will enable code generation, conditional code inclusion etc. Useful when starting to support other platforms - same library file will support both x86 and ARM.

• static if ... end
• static while ... do ... end
• static ... end

`msleep` should divide input into seconds and nanoseconds for bigger accepted input range

Code to improve:

stacky/std/time.stacky

Lines 22 to 26 in cb31882

	msleep fun # miliseconds --
	timespec timespec.tv_sec + 0 store64
	timespec timespec.tv_nsec + swap 1000000 * store64
	while timespec timespec SYS_nanosleep syscall2 0 < do end
	end

Turn `1 +` into `inc` (same for `1 -`)

https://www.felixcloutier.com/x86/inc

16, 32 and 64 bit memory declarations

Currently supported: []byte

• Rename []byte to []uint8?
• Add []uint16, []uint32, []uint64
• Add pointer sized arrays and declarations isize (in C ptrdiff_t) and usize (in C size_t)

Should follow convention in #28

`define_words` rewrite

Current code is a bodge over bodge, let's fix that!

Dead code elimination: loops, returns and conditions

For infinite loop and return statements all code to nearest jump after loop / return may be deleted

For always true if condition else branch may be removed, similar always false condition may remove then branch

Control flow visualisation

Inspired by Tsoding's Porth control graph feature

Return, break and continue statements

• return quits early function
• break quits from loop
• continue jumps to while in given block

Related: #24

Output binary file padding directive

Bootsector has to have specific size, so padding directive is needed e.g. <desired-size> define-padding.

512 define-padding

will be same as NASM:

times 512 - ($-$$) db 0

Basic type system

Program is compile time evaluated. Evaluation starts with empty type stack. All operations consume and/or produce values and place their types onto type stack. Illegal are:

• ending program with types on type stack.
• trying to pop value from empty type stack
• violating rules for control flow
• mismatching types from required by operations

Operations can have different meaning and result according to types that are on stack. Stack manipulation operations (like drop or swap are supported by all operations).

Types

Type system should support following types:

• bool (result of comparison operations)
• u64 (integer literals, syscall result)
• ptr (string literals, memory declarations, address of function)

Casting syntax is as(bool), as(ptr) ...

Control flow

if blocks

Value consumed by if for determining which branch to execute known as condition should be bool.

• with else data stack types must match on both ends. typeof(then_branch) == typeof(else_branch). Condition and it's type is consumed
• without else data stack must match stack before if with condition value consumed.
  For program <code> <condition> if <then_branch> end must hold typeof(code) == typeof(then_branch)

while blocks

Stack after consuming condition in do should match this before while. Stack after loop body execution should match this before while.

functions

On each return (including function end) state of stack should be the same. if return is embeded into while or if, it should change behaviour of given block checking.

• When in if branch with return do not have to produce the same stack as other branch or code before.
• When in while stack don't have to match stack before while

Operations and their types

Operations on u64

Basically almost all. Excluded are:

• or, and, call
• store and load only accepts ptr as address
• do and if requires bool as conditions

Operations on ptr

• ptr - ptr -> u64 - (assumes first ptr is the bigger one, otherwise we are in trouble)
• ptr - u64 -> ptr
• ptr + u64 -> ptr and u64 + ptr -> ptr
• equality with ptr and u64
• casting to bool meaning ptr 0 !=
• ptr load<n> -> u64
• u64 ptr store<n> -> void
• syscall<n> should support ptr for it's data arguments (function wrappers will provide stronger typing for syscalls in the future)
• ptr call -> ? - such type system cannot express result of call

Related

Different size and "signedness" of types: #46
Function type specification: #47

Dead code elimination: Do NOT emit functions that are unused

Exhaustive signal numbers list

Definition below is not exhaustive:

stacky/std/posix.stacky

Lines 381 to 394 in cb31882

	SIGHUP 1 constant
	SIGINT 2 constant
	SIGQUIT 3 constant
	SIGILL 4 constant
	SIGTRAP 5 constant
	SIGABRT 6 constant
	SIGFPE 8 constant
	SIGKILL 9 constant
	SIGUSR1 10 constant
	SIGSEGV 11 constant
	SIGUSR2 12 constant
	SIGPIPE 13 constant
	SIGALRM 14 constant
	SIGTERM 15 constant

More signal numbers can be found at: https://fossies.org/linux/glibc/sysdeps/mach/hurd/bits/signum-arch.h

Move standard library from C++ to Stacky

All definitions below should be implementable in Stacky

stacky/stdlib.cc

Lines 42 to 91 in 4a5e50a

	static inline unsigned digits10(std::uint64_t v)
	{
	unsigned result = 1;
	for (;;) {
	if (v < 10u) return result;
	if (v < 100u) return result + 1;
	if (v < 1'000u) return result + 2;
	if (v < 10'000u) return result + 3;
	v /= 10'000u;
	result += 4;
	}
	}
	extern "C" {
	void _stacky_print_u64(std::uint64_t v)
	{
	char buffer[std::numeric_limits<decltype(v)>::digits10 + 1]{};
	unsigned const len = digits10(v);
	unsigned pos = len - 1;
	while (v >= 10) {
	std::uint64_t const q = v / 10;
	unsigned const r = v % 10;
	buffer[pos--] = '0' + r;
	v = q;
	}
	*buffer = v + '0';
	buffer[len] = '\n';
	posix::syscall(posix::Write, posix::Stdout, (uint64_t)buffer, (uint64_t)len + 1);
	}
	void _stacky_exit(int exit_code)
	{
	posix::syscall(posix::Exit, exit_code);
	}
	void _stacky_newline()
	{
	char nl = '\n';
	posix::syscall(posix::Write, posix::Stdout, (size_t)&nl, 1);
	}
	void _stacky_print_cstr(char const *cstr)
	{
	auto p = cstr;
	for (; *p != '\0'; ++p) {}
	posix::syscall(posix::Write, posix::Stdout, (size_t)cstr, p - cstr);
	}
	}

Write and read operations other then 8bit

Add support for 16, 32 and 64 bit writes and reads.

stacky/stacky.cc

Lines 613 to 626 in 880ae23

	case Word::Kind::Read8:
	asm_file << " ;; read8\n";
	asm_file << " pop rax\n";
	asm_file << " xor rbx, rbx\n";
	asm_file << " mov bl, [rax]\n";
	asm_file << " push rbx\n";
	break;
	case Word::Kind::Write8:
	asm_file << " ;; write8\n";
	asm_file << " pop rbx\n";
	asm_file << " pop rax\n";
	asm_file << " mov [rax], bl\n";
	break;

Strings should be in .rodata

Currently strings are placed in .data, but they need to be allocated in .rodata. This way we could have one string allocated for every same string literal without fear of corrupting by some write operations

REP assembly instructions as words

• memcpy rep movsb (allows other sizes then 8bit)
• memcmp repe cmps (allows other sizes then 8bit)
• strlen, strchr REPE SCAS

Investigate further REP instruction family

Compilation modes

Add compilation modes listed below:

• build - compile program for 64-bit Linux
• build-os - compile program for 64-bit mode that is bootable
• run - same as build but runs program after compilation

arguments parser: Boost Program_Options

Parse escape sequences in string and character literals

Seperate concept of tokens, words, keywords and instrinsics

Currently Word is both token type for lexer / parser and operation type. Separate them.

Token types:

• String literal
• Integer literal
• Word

Intrinsics are just predefined words, but can be overwritten by the user (keywords cannot)

Don't emit unnesesary labels

For later optimization, knowing which statements are part of unbroken continues execution is crucial

Integrate test runner `run-tests.cc` into stacky compiler

Definitions must have ability to appear in any order

To do it define_words must have ability to wait for other definitions to evaluate first and change content of function bodies after function formation

Functions explicit typing

Introduces 2 new keywords

• -- - marks split between input and output stack parameters
• is - marks end of function type definition

Examples:

add2 fun u64 -- u64 is 2 + end

pswap32 fun ptr ptr -- is ... end

seconds2ymd fun u64 -- u64 u64 u64 is ... end

3dup fun 1 -- 1 1 1 is 2dup dup end

swap fun 1 2 -- 2 1 is ... end

When numbers are used inside of type definition they refer to generic type parameters known at compile time.

2021-11-05: Don't add type variables for now

Ramaining comparison and boolean operators

Warning for code after infinite loop

Binary, seximal, octal, hexadecimal integer literals and digit separators

Base	Integer literal regex
Binary	0b[_01]+
Seximal	0s[_0-5]+
Octal	Oo[_0-7]+
Decimal	[_0-9]+
Hexadecimal	Ox[_0-9a-fA-F]+

Split compiler into multiple translation units

Compilation is already unnecessary slow, and in #37 we are gonna bring more heavy Boost code to compile by not so fast gcc

More stack manipulation operations

• dropn where n >= 0
• drop - drop element from the stack
• over - ( a b -- a b a )
• rot - ( a b c -- b c a )
• tuck - ( x1 x2 -- x2 x1 x2 ) - copy the first (top) stack item below the second stack item
• 2drop
• 2swap - ( a b c d -- c d a b )
• 2over- ( a b c d -- a b c d a b)

Constant folding in array size declarations

Make expression Buffer Size 1 + []byte work

Call word and function address

• &<function_name> - push address of function_name onto stack
• &fun <code> end - declare function and push it's address onto stack (anonymous functions)
• call - jumps to function that is pointed by top of the stack

Change order of arguments for []byte and constant

Identifier should be first for ease of grepping Stacky source files

Buffer-Size 1024        constant
Buffer      Buffer-Size []byte

Find all buffer related definitions grep -rn '^\s*Buffer' *.stacky

Make compiler verbose!

Print information about optimizations, included files, code generation itp

Dead code elimination: unused strings

Issues #39 and #40 may remove all push string address operations. Remove unused strings

Simplification of binary operations definition

Most binary operation asm definition follows pattern pop pop <operation> push.

Special words for file, system etc. information

• _File - name of file
• _Line - current line
• _Column - current column
• _Date - date of compilation

Enables providing language defined assert

Empty string do not parse

"" produces error "Missing terminating " character". std::adjacent_find is not the best choice after all?

Time & date functionality

New words

• now - pushes number of seconds since 00:00 1970-01-01
• +minutes, +hours, +days, +months, +years
• -minutes, -hours, -days, -month, -years
• date - (seconds -- year month day hour minutes)

Implementation details

• [clock_gettime](https://man7.org/linux/man-pages/man2/clock_gettime.2.html)

#include <unistd.h>

constexpr unsigned Clock_Gettime = 228;
constexpr unsigned
	Realtime_Clock = 0,
	Monotonic_Clock = 1;

#include <iostream>

int main()
{
	std::uint64_t buf[2];
	syscall(Clock_Gettime, Realtime_Clock, (uint64_t)&buf);
	std::cout << "sec: " << buf[0] << " nsec: "<< buf[1] << '\n';
}

Max, min

Using conditional move instruction.

Generated asm from C for min function:

cmp     rsi, rdi
mov     rax, rdi
cmovbe  rax, rsi
ret

`noreturn` keyword and type

Type related construct. noreturn keyword should behave similar to return in function given types. Useful for typing exit since it cannot return and code like 0 SYS_exit syscall1 drop is silly

Include statement

Includes file directly, like C #include.

• "stdio.stacky" include-local for inclusion of files relative to source file
• "stdio" include similar to include-local but includes also files from standard library and tries to append .stacky if file is not found

Better string parsing

Currently string is any sequence within " without any escape sequences parsing. This probably requires change to treatment of sval field in struct Word or offloading parsing to NASM.

NASM support for escape sequences: 3.4.2 Character Strings.

Current broken string support:

stacky/stacky.cc

Lines 206 to 212 in 880ae23

	if (ch == '"') {
	word.kind = Word::Kind::String;
	auto str_end = std::find(std::cbegin(file) + i + 1, std::cend(file), '"');
	if (str_end == std::cend(file))
	error(word, "Missing terminating \" character");
	word.sval = { std::cbegin(file) + i, str_end + 1 };

Random number generation

• Add rdrand instruction as random64 and random32
• Add uniform64 and uniform32, such that b a uniform returns integer in [a,b] with probability of 1 / (b - a + 1)

See also

• RDRAND
• RDSEED
• std::uniform_int_distribution
• https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
• https://lemire.me/blog/2016/06/30/fast-random-shuffling/
• https://arxiv.org/abs/1012.4290

Turing completness

Prove that language is Turing Complete using Rule 110.

Sized string literal

$"<str>" produces stack: ( address(str) len(str) )

Hello world with this syntax:

$"hello, world" 1 1 syscall3

Character literals

• Add character literals similar to C syntax '<character>'
• Character literals can accept escape sequences (maybe same solution for this and #4)
• Character literals can be multibyte, ab = little_endian('a', 'b') = 0x6261. This makes possible 'hello\n\0' top print. Each character is one byte. Literal is padded with 0 to be 1, 2, 4 or 8 bytes long

Import should namespace symbols in included files

For example "io" include should define io.print not print. Question is what about operations like .?

Stderr and exit code assertions, and general output compare in test runner

Boost.Process allows for easy stderr and stdout capturing

#include <iterator>
#include <boost/process.hpp>

namespace bp = boost::process;

int main()
{
	bp::ipstream standard_out, standard_err;

	bp::system("<command>", bp::std_out > standard_out, bp::std_err > standard_err);

	std::string out { std::istreambuf_iterator<char>(standard_out), {} };
	std::string err { std::istreambuf_iterator<char>(standard_err), {} };
}

Sized and (un)signed integer types

Removes ptr

Introduces

• New types
  • Unsigned: u8, u16, u32, u64, usize
  • Signed: i8, i16, i32, i64, isize
  • Pointers: written with * before type, for example: *u32
• Typed integer literals (like 1u64, 0xdead_i32)

usize and isize are type aliases for type that matches their bit length. For example isize == i64 <=> sizeof(isize == i64)

Memory declarations produce pointers with correct type. For Foo 1 []u32 holds typeof(Foo) == u32

Conversion from smaller type to bigger type is implicit given their both (un)signed. (Not sure about this, time will tell)

Pointers

Addition, subtraction, load, store have different meaning according to what pointer is pointing to.
For example: *i32 + u64 is val(*i32) + 4 * val(u64) (same as C)

User defined static arrays

Currently we have predefined heap array. Better would be syntax for compile time array word definition. For example:

1024 buffer define-bytes
buffer 1 poke
buffer 1 + 255 poke
buffer peek buffer 1 + peek + .

Print current state of program during compilation

For debugging purposes provide options to print state of program (current word collection)

Waits for #7