PolyStack

PolyStack is an esoteric programming language and Domain-Specific Language designed to serve as the Type System for other programming languages, particularly stack-based ones. It aims to be a powerful type system for stack- and deque- based languages, itself being deque-based. It aims to be so powerful, in fact, that it is hoped to be Turing-complete in its final form.

Syntax

PolyStack is similar to any other concatenative programming language, having an RPN format for its instructions. In order to thoroughly integrate with W, the language for which it was primarily defined, it does some fiddling with the logical syntax; however, an alternative standalone syntax is also available.

As a stack-based language, the commands are a series of instructions separated by spaces. In the default version, quotes delimit a quoted string, which can be pushed onto a secondary stack, whereas in the alternative version, there are no quotes. All other instructions are commands; either types (which just push their type onto the stack) or manipulation commands (which actually do stuff).

The primary stack can hold three things: Scalar Types, Type Classes, and Compound Types. Scalar Types are the types of scalar data; for example, Int or Float or Char. Type classes represent sets of types, such as Num. Compound types are full type expressions; the type of a function in Haskell. A Compound Type might be (Char Int -- Float) or (Ord x) => (x..y -- y..x). Unlike Haskell types, which return exactly one value (which may be a collection, but is one value nonetheless) from a single list of inputs, PolyStack types accept two lists of inputs and two lists of outputs, representing the values POPed and the values PUSHed. This means that PolyStack types can return multiple values, though this can be constrained in implementations.

An example of a PolyStack program is:

"x" pmt Ord <-> constrain <| ?<

Which always returns True through a convoluted process.

Type Expressions

Type Expressions in PolyStack are based off of Forth's type expressions. They are of the following form:

(Tc1 x, Tc2 y, Tc3 z) => (a b..c d -- e f..g h)

This tells the computer the following:

• The polymorphic variables x, y, and z must belong to the typeclass Tc₁, Tc₂, and Tc₃, respectively
• The arguments of types a and b are POPed from the front of the deque (first b, then a)
• The arguments of types c and d are POPed from the back of the deque (first d, then c)
• The results of types e and f are PUSHed onto the front of the deque
• The results of types g and h are PUSHed onto the back of the deque

Argument types can be either polymorphic (lowercase) or static (capitalized). When padded in square brackets, they form a list; in curly brackets forms a set, and a comma-separated list in parenthesis forms a tuple. A type of the form {a:b} is a dict mapping elements of type a to type b, and if the curlies are replaced with square brackets it forms an ordered dict of the same type. Finally, an argument can be another type expression padded in parenthesis.

Builtin Types, Type Classes, etc.

A list of the Builtin Type Classes is:

Name	Recommended Usage	Constraints
Num	For numbers that can be manipulated: added, subtracted, etc.	Ord
Ord	A value which can be compared (is this greater than/less than/other) another value?	Eq
Eq	Are these two values equal?	N/A

The builtin types, and the classes they belong to, are:

Name	Meaning	Type Classes
Int	A number positive or negative; just must not have a fractional part	Num
Float	A real number; any number, really.	Num
Complex	A number with both a real and an imaginary part (both floats)	Num
Char	A single Unicode character (any plane)	Ord
String	[Char]	Ord
None	A null value; no data.	N/A
Some	A non-null value with no data	N/A

Commands

This section covers the commands available to the user in PolyStack.

Deque Manipulation
Command	Laconic	Meaning	Type
DUP	:	Pop a value, push it twice	(a -- a a)
DROP	$	Pop a value, discard it	(a -- )
SWAP	\	Pop two values, push them s.t. they are reversed in order	(a b -- b a)
ROLL	|>	Pop a value, move it to the back of the deque	(a -- ..a)
REVROLL	<|	Eject a value, move it to the front of the deque	(..a -- a)
PAD	<->	Pop a value, push it at both the front and back of the deque	(a -- a..a)
BACKPAD	<~>	Eject a value, push it at both the front and back of the deque	(..a -- a..a)
Scalar Types
Command	Laconic	Meaning	Type
(Typename)	N/A	Push the type of that name	( -- a)
POLY	~	Pop a string from the secondary stack, push it as a polymorphic variable on the main stack	( -- a)
Compound Types
Command	Laconic	Meaning	Type
LIST	[]	Pop a type, push its list type	(a -- [a])
TUPLEn	(,,,) (with n commas)	Pop n types, push them in a tuple	(*a -- (*a))
Type Classes
Command	Laconic	Meaning	Type
(Typeclassname)	N/A	Push the typeclass of that name	( -- a)
?<	N/A	Pop a type, pop a typeclass, push Some if that type is in that typeclass, else push None	( -- a)