The Impossible! Language

The Impossible! language has been developed with the purpose of writing a expressive language that is able to support the functional paradigm of OCaml as well as many types from OCaml library. Another characteristic of this language is the complex syntax, with many short operators that does different things, it can be considered an esoteric language.

This language is compiled into functions during the parsing phase and then executed as normal OCaml code, this means that opcodes are interpreted but behavior is almost native. It is type-unsafe but with strong types (with some exceptions related to implicit conversion between numbers).

The interpreter has a top-level mode in which it is possible to execute some simple statements, e.g. to set an environment variable or ask help about an operator. Every command must be specified on its own line. Everything else is considered code and compiled accordingly.

Note: this guide is far from being complete or accurate yet (this also because it is still in evolution). The language, for now, is meant to be self-explanatory through the inline reference that can be used directly from the interpreter itself. Feel free to explore the various instructions without relying just on this page!

Introduction

As soon as you launch the executable (that can be downloaded here ) you will be prompted with

i>

Here you can do two things, write code or execute a top-level command like help (that, for example, prints the available commands). If you type instead something that is not a command like

i> 2 3 +

you will obtain:

5 : int

This because the program is interpreted and evaluated: you are calculating the sum between 2 and 3, the result is 5 and it is printed out on terminal.

The Virtual Machine

The virtual machine is a stack-based one. This means that whenever the interpreter finds a value in the program it will push it onto the stack and last inserted item will be the topmost one. We indicate the head of the stack with <- .

When the virtual machine is started the stack is empty:

empty <-

Executing a simple program like 2 4.5 will first push an int value onto the stack, and then push a float . This will produce the following situation:

2 4.5 <-

So 4.5 will be the top element. Ok, this program wasn't so useful: let's actually compute something. Adding just a plus operation as in 2 4.5 + will first push both values, then pop them to calculate 2 + 4.5 and store the result as a float to obtain the following situation:

6.5 <-

Whenever an instruction, that is defined by a signature, is executed, the value are popped out of the stack and used as arguments to the instruction in reverse order (not the stack FIFO one). Let's make an example: suppose the operation extract that gets a substring of a string according to a numeric range. Its signature is

string -> range -> string

So, according to what we said before, we can push them in the same order and execute the instruction:

"foobar"0..2|
  "foo" : string

Stack Instructions

Since everything is achieved through to the stack, the language provides some instructions, referred as stack instructions , that are used to do basic things often useful while writing any program. There are 8 operators:
  • ,   Trash the topmost element of the stack. The value is lost forever. ( ,, can be used to drop the whole stack)
  • ;   Dupe the topmost element of the stack. You basically clone an element to obtain two copies.
  • %   Swap the first item of the stack with the second. You basically push topmost item down and make the one below emerge.
  • $   Pick the n-th element of the stack with n that must be pushed on the stack before the execution and it is zero based. This means that pushing 0 correspond to executing the dupe operation. While using 1 will clone the second element and so on..
  • #>   Rise the third element by placing it in top position. The previous first becomes second, and similarly for the previous second element.
  • <#   Sink the top element by placing it in third position. The previous second becomes first, and similarly for the previous third element.
  • ^   Peek the topmost item and prints its value without removing it from the stack.

  • ^^   Print the topmost item after having removed it from the stack.

Interactive Mode

While the language can be used to write stand-alone programs it is also possible to use the VM interactively by invoking its executable. Once started it shows the Impossible! console with the following prompt

i>

From here it is possible to write plain code which operates on stack and variables that are carried between every executed line. In addition it is possible to use special instructions that are allowed only on their own lines. For example typing help command will show a description of all basic commands available to the shell.

Other commands are stack that prints out the stack content or wipe that clears the whole stack trashing all contained values.

Up to now the various commands, except for the inline help, are being designed and tested. They are not fully functional (especially the debugger) so don't rely on them.

The best way to learn the language is to use the inline help, it can be accessed either by value type either by operator, you are allowed to try it out yourself by typing for example help .>. or help list and see the reference.

Functional Way

Impossible! language has some features in common to functional languages. This is useful to permit elegant still obscure development. Functions are values and they are used as every other data type, they can be indeed stored onto the stack and used with all the operators provided.
A lambda function is defined by wrapping its code in brackets, so [] is the simplest function possible that just does nothing. Whenever the compiler finds a function definition, it pushes it onto the stack. Of course this function would be useless without actually applying it to arguments.
To actually use a function you need to use the apply ! operator that pops last value from stack and, providing it is a function, it starts its execution.
We can define a function that adds 2 to a number and apply it to 4:

4[2+]! #=> 6 : int

or a function that adds three numbers:

1 2 3[++]! #=> 6 : int

Every lambda value is first stored onto the stack and then used with instructions as everything else. This mean that we can easily manipulate them

[2*]3 1$ ! % ! => 12 : int

In this situation we clone the function and we apply it twice chaining execution on 3 and on the result of first call.
We also have two different functional options to work with lambda calls:
  • !!   Currification of function
  • !!!   Uncurrification of a function
These two instructions are used to carry out partial application and the opposite operation. A partial application is a higher order function that, taken a lambda value, produces a new lambda in which a parameter has been bound inside the call.

If we have, for example, a lambda that sums two numbers [+] , we can partial apply 2 to it to obtain a new function that pushes 2 onto the stack and then behaves like the generic version.

Since lambdas are values, they can be used pervasively while writing programs, for example

{:}'+[+]<-'-[-]<- 2 2 2$'+->!

will create a map that maps characters + and - to two functions that execute the addition and subtraction. Then the stack is used to retrieve the addition and this latter is executed on two values on stack. This characteristic allows Impossible! to write interpreters for other esoteric languages, even itself.

Note: the short syntax for maps {'+:[+],'-:[-]} wouldn't work because of a restriction: a function can't be hard-coded inside a collection (it will be adjusted).

Conditionals and Iteratives

It's is possible to use both the if and if/else constucts in a simple way: two operators are used. They both work by popping a boolean and executing successive lambdas according to the truth.
If ?
This instruction requires a bool that will decide if the next lambda on the stack will be executed. For example [5>[t^^]?] will print true : bool if a number over 5 is passed to the function. The instruction will just discard the provided lambda if boolean value is false.
If/else ??
This instruction requires a bool that will decide if which of the next lambdas on the stack will be executed. For example [2//0=>[t^^][f^^]?] will print true : bool or false : bool according to if the number is even or odd.

These two are good to do just a choice, what about loops? Since everything resembles a functional structure usually it's enough to use the provided .> iter instruction that loops over every kind of enumerable type (range, list, string, etc.). A classic while operator is provided when built-ins are not enough:

While <>
This instruction requires two lambdas onto the stack, it will use first lambda to check if the break condition has been reached (function must push" false : bool before finishing) and execute the second lambda until the condition remains valid. For example [30@>;15=~][^^]<> will toss random numbers in range 0..29 and prints them until 15 is found.

Math

Numbers

The short story: the language supports 3 kinds of numbers: integers, floats and complex numbers. The language is dynamically-typed, since there is just a stack and correct instruction will be executed according to operator syntax and types on stack but it is NOT weak typed. There is some type coercion between numbers that widens the number type:

2 1.4+
  3.4 : float

but nothing more. Conversions can be done with specific operators (eg.  .>: ). This is a design choice, to be able to distinguish more operations and provide different semantics on float and int types.

All numeric types support the same set of basic operations as described in the following table (first binary, then unary operators):

Name Code Stack before Stack after Description
x y < z <
Add + z = x + y
Sub - z = x - y
Mul * z = x * y
Div - z = x / y
Pow ** z = x y
x < z <
Neg _ z = -x

Collections

Basic operations over collections are the following three, which are high-order functions over lambdas themselves, the syntax of the operator resembles what the function does.
Each .>
This operation loops through the collection by calling the supplied lambda for every element inside it. It is used when you want to work on every item without producing any output, it takes an element and produces nothing so the syntax is

When writing the lambda used in conjunction with this operator you have to think that the interpreter will let you find the current element already pushed on the stack and it is your duty to consume it (otherwise the stack would get filled).

Map .>.
As the name suggests, it is used to map every item of a collection to another one. This can be useful really often whenever you need to modify every element of the given collection according to a specific function. So this kind of operation takes the current element and produces a new one, this is way the syntax is
A simple example:

{1,2,3,4}[2*].>.

This will produce a new list obtained by multiplying by 2 every element. Map function takes a collection and a lambda and push the resulting new collection.
Fold :>.
Finally the fold operation, which uses a lambda that combines two values: one is the current element, the other is an accumulator value which is given as another parameter. The initial value is passed to the fold function together with the collection. An example that sums all the numbers of a list:

{1,2,3,4,5}[+]0:>.

At first, element function gets 1 and 0, then computes 1 so that second will get 2 and 1, etc. This function takes a collection, a given initial value and a lambda and leaves a final value on the stack.

List

Lists are arbitrary size collections that can be instantiated directly in code as in {1,2,3,4,5}, where {} denotes the empty list. In Impossible! they are not restricted by type and can be heterogenous, containing any kind of value at the same time, even other lists.
Many operations are available on lists, let's summarize them in the following table:

Array

-

Set

Sets are similar to lists but they don't allow duplicates inside themselves; adding the same element twice, indeed, won't have any effect on a set.
Their definition is very similar to the previous one: {;1,2,3,4,4,5} will push the set containing five integers from 1 to 5. As you can note the only difference is the presence of a semi-colon ; before the first element. In addition, as we stated before, the second 4 used in declaration will be automatically discarded.
The aim of this data structure is to allow fast operations on sets like union, intersection or difference in opposition to lists for which these operations are implicitly expensive. The empty set is denoted by {;}

Map

-

Ranges

A range data type is available, that is stored internally as a list of pairs of integers, each one representing an interval contained in the range. Some basic operations are available on ranges, like union or intersection, which will take care about overlapping intervals accordingly. They are also useful to do mass retrieves over collections as you will see in examples. Negative ranges are accepted by parser but the behavior is still undefined when used in concomitance with other types.

The syntax is the double dot, for example 1..3 will be the range composed by 1 2 3.

Vector Algebra

Basic vector algebra is being implemented, it will consist of types as vector2 or vector3 . They will be possibly enhanced by transformations or quaternions.