Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Antsan]

Hey, look guys, I made a programming language:
Repository for... let's call it a specification
And here is the repository of my implementation of poslin

Spoiler: An intro (click to show/hide)

Poslin is a contraction of "postfiksa lingvo", which is Esperanto for "postfix language".
As the name implies, poslin is a stack based language, a bit like Forth. Like Forth poslin allows you to access the return stack, which can make for some fancy programming.
Poslin relies heavily on meta-programming. There are no keywords and the syntax is as minimal as it gets. Actually, the only syntax there is are strings, numbers and symbols. Most of the syntax used in poslin is implemented in the language itself.

The language makes a distinction between immediate and delayed operations.
Most operations are delayed symbols and you need to tell poslin when you want to do something with an operation.
A few operations are immediate. If the name of an immediate operation is read by the reader the corresponding thread is executed, well, immediately.

This scheme allows some fancy stuff, like implementing comments in the language itself.

Spoiler: The specification (click to show/hide)

If you only want to play around with the language a bit, you don't need to read this.

Now, the so-called specification is not very much of one right now. Actually it's just two files with tables of operations names with some very minimal documentation.
I wrote those just so I knew what I was doing while implementing the language.
The two files are in the "spec" subdirectory of the repository.

The repository also contains an implementation of the first part of the standard library of poslin. This is the file "libs/base.poslin" in the repository.
When I started planning the language, I wanted to implement as few operations as possible in the implementation language. So, without this file poslin is actually quite hard to write and the resulting code is exceptionally hard to read.
This has the advantage, that a possible implementor of the language needs to implement only 49 64 82 primary operations and then can load the standard library to have fancy syntax at his fingertips.

Now for a few technical details.
The operations in poslin are, technically speaking, mappings from symbols to an immediateness value and a thread. The immediateness value is a boolean that determines whether an operation is immediate or not and the thread (terminology taken from Forth actually the term "threaded code" is a kind of calling convention or rather the lack of a calling convention; Wikipedia knows better than me; my implementation of Poslin in Common Lisp uses cons threaded coded, which is a fancy way of saying that the addresses of the operations to be called are stored in an ordered binary tree) is the "function" that is called when the operation is called.

Basically there are always two (or three, if one counts the program counter, which can only be set but not read) structures available: the path and the return stack.

The program counter (from here on out "pc") contains the thread that is currently running. A thread consists of a front part and a back part. If the front part is not a constant or a primary thread then the back part is put onto the return stack (from here on out "rstack"). If the pc is finally empty, the rstack is checked for the next thread to put into the pc. If the return stack also is empty, the program is finished running/the REPL asks the user for further input.

The path is a stack containing so-called environments.
An environment is, first and foremost, an immutable structure. It is also a map from symbols to bindings, with the twist that an environment can have a parent environment - if something isn't found here it is looked up in the parent environment.
Bindings are the only mutable structures in poslin (not counting the path, rstack or pc) and are used similarly to pointers. Other mutable data structures might be introduced in the further development of poslin or by non-standard additions to the language.

An environment that is lying on the path needs to contain at least entries under the symbols STACK, OP, IMM and FEATURE.
The binding of STACK always needs to contain, well, a stack. This stack is where everything that is not called ends up at first.
The binding of OP contains an environment. This is the environment in which the thread of an operation is looked up.
The binding of IMM also contains an environment. Here the immediateness of operations is stored.
The binding of FEATURE is also a stack. This stack contains a few symbols describing what features are available in the currently running poslin. In most cases it will contain the symbol PRIM, showing that the primary operations are available. If you know Common Lisp: This is similar to Common Lisp's *FEATURES* variable.

As I said the path contains a stack of environments. The previously defined slots are always looked up in the environment on top of the path, meaning that you can push an environment onto the path where those slots are filled with entirely fresh structures, so for instance you can open a local stack or temporarily use a different set of operation definitions or even change which operations are immediate or not.
Other slots can be freely defined. The standard library, for instance, introduces the VAR slot to provide an environment for storing variables.

Spoiler: Using the implementation (click to show/hide)

For Linux users with an x86-compatible kernel: You can download a binary distribution in the "Downloads" section now.

For anyone else (and those who want to use the source either way):
To run this implementation you first need some implementation of Common Lisp. I have only tested this on SBCL, but I don't use any special non-standard features in my own code, so it should run on any standard compliant implementations that also support cl-ppcre (I am not sure that this one runs on any standard compliant implementation).
You are advised to install quicklisp, too, as it eases the process of installing the whole thing.

As soon as you've got Common Lisp running with quicklisp, put the source tree of poslin (use the "no-external" branch of the repository branches have been changed so that the default branch can be used) somewhere where quicklisp can find it (one such location is the "local-projects" folder in the installation directory of quicklisp) and load it form the Common Lisp REPL via

Code: [Select]

> (ql:quickload "poslin")and poslin should be loaded.
Then you can start the basic REPL of poslin (not containing the standard library but only primary operations) via

Code: [Select]

> (repl0)If you want to have the standard library available, download the file base.poslin from the specification repository, put it in a folder of your choice, open up the file "source/repl/repl.lisp" of the implementation and change the following function definition:

Code: [Select]

(defun repl1 ()
  (repl (new-poslin *prim*)
"~/src/Poslin/lib/base.poslin"
))so that instead of "~/src/Poslin/lib/base.poslin" you've got the path to where you saved base.poslin
Now you can load poslin again and run the poslin REPL containing the standard library via

Code: [Select]

> (repl1)

Spoiler: A small tutorial as intro (click to show/hide)

This assumes you already read the intro and started the REPL. Currently there is no way to load poslin code from a file from inside the REPL. To load a file containing poslin code, do the following in the REPL:

Code: [Select]

""
/path/to/poslin/file" load !

If you didn't do anything the REPL currently looks like this:

Code: [Select]

[ ]
>
The square brackets show you the contents of the current stack (it is empty, so there is nothing to see here) and the '>' only signifies that Poslin is waiting for input.
So, let's dive right in and type the following:

Code: [Select]

1 2 +and press enter.
Your REPL should now look like this:

Code: [Select]

[ 1 2 + ]
>
If you wonder why the stack now looks like this, remember that most operations in poslin are delayed and not immediately called when they are encountered. '+' can hardly be seen as part of the syntax, so it isn't immediate.
To actually do the addition, now enter the following:

Code: [Select]

!and press enter (this is the last time I am writing this - not that I don't think that you won't get the idea by yourself, but one can never be too sure).
Now you've got the following:

Code: [Select]

[ 3 ]
>
'!' is an immediate operation. It in itself takes one argument. It first converts this argument into a thread (for symbols by looking them up, for stacks by converting them into a thread by certain rules, for threads by just taking their identity, for everything else by creating a thread which constantly returns the value consumed) and then puts that thread onto the program counter, so that the thread runs.
In short: '!' is the operation to call when you want something to be done.
'clean-curr-stack' is an operation that replaces the current stack with an empty one, so call that now. Keep in mind that 'clean-curr-stack' is not immediate.

After you have done that you will probably want to know how to define an operation yourself.
There are several ways to do this.
Here's the first one.

Code: [Select]

2+ ;[ this is the name of the operation to be defined - by the way ';[' is an immediate operation that makes sure that after it only '];' is an immediate operation that puts you back into a mode where you can program again ];
[ 2 + & ;[ we open up a stack, put 2 and + on it and then convert + into a thread that gets put back. If we didn't convert + into a thread, this operation would just put 2 and + onto the current stack when called ];
]o ;[ this closes the current stack, converts it into a thread and defines it as an operation with the given name ];
Keep in mind that in poslin whitespace is just whitespace and carries no greater significance than keeping tokens apart from each other. Keep also in mind that it is the only thing keeping tokens apart from each other - brackets and parentheses aren't special in this regard.
You can now try this function:

Code: [Select]

[ ]
> 5 2+ !
[ 7 ]
> __ !
[ ]The operations defined in this way always work on the current stack.

[Antsan]

So, for the second part of the tutorial, now that the technical problems have been resolved.

There now is an executable for Linux available. You can find it in the "Downloads" section of the implementation repository. Use the script in that file to run the REPL.
The repository of my implementation has been changed so that you don't need to use the "no-external" branch. Using the "default" branch should be fine.

Something I forgot to mention: You can quit the REPL by simply entering 'QUIT' and pressing enter.

Before we go on, let me explain how 'if' works in poslin.
First, the symbol 'if' itself is not associated with any value. These roles are for the symbols '<?>' and '?'.
Poslin is written in strict prefix notation. That means, that there is no way to write something like

Code: [Select]

<?> test then elsebecause that isn't prefix. The '?' would need to know about stuff that it cannot know about, because that stuff isn't on the stack when '?' is called.
That's why it looks like this:

Code: [Select]

boolean then else <?>
'<?>' is something of a bare-bones version of an if. it takes the three arguments and then decides whether to put the then or the else back. It does nothing else.
'?' is a bit (but only a bit) more sophisticated: After putting one of the branches back on the stack it calls '!' on it. It is also what I call a macro in poslin. It is immediate, but the effect of it being called is leaving the right threads on the stack, so it can be conveniently used in an operation definition.

Another way to define operations is a bit more idiomatic and might look almost like a more regular language.
The factorial looks like this:

Code: [Select]

factorial
{ n arg ;[ this makes an argument called 'n'. It doesn't matter in this instance, but it is important to remember that defining arguments like this will take those arguments from the stack in reverse ];
  n get 1 <= & ;[ check whether n is smaller than or equal to 1 ];
  1
  [ n get 1 - & ;[ I open up a new stack here because '?' takes exactly 3 parameters, so this stack is used to construct a thread, which is only one object ];
    factorial call ;[ '&' can be called 'inline'. Inlining doesn't work for recursive function calls and 'factorial' cannot be inlined, because it isn't defined, the we use 'call' instead. ];
    n get * &
  ] & # ;[ first the stack we just wrote is turned into a thread and then that thread is made into a thread that constantly returns just that thread via '#'. We cannot leave the thread itself lying around, because then it would be called instead of being put onto the stack ];
  ? return
}
To give you an idea what's going on:
'{' is actually no different from ']', but operation definitions look nicer if the curly braces are balanced.
'}' does a lot of stuff. One of these things is to make sure that the defined operation will use it's own local stack when it runs. Another is to make lexical environments for operations, variables and immediateness, so one can use local variables in this operation and be sure that the meaning of the operation doesn't change when it is called somewhere, where some things might be defined differently - this is especially important for recursion to work.

Spoiler (click to show/hide)

This thing about recursion is actually what caused the technical problem - I was reusing he same environment for all calls of a given operation defined with this, which meant that everything was happening on the same stack when recursive functions where relying on recursive stacks being used.

'arg' is a macro that leaves threads to pop an argument from the parent stack (the stack that is the current stack just before you open a new local one) and defines this as a local variable of the given name.
'get' is a macro that returns the thread for 'ev~:', which looks up a variable in the current variable environment.
'call' is a macro that returns the thread of '!'. We could use it for any operation used in an operation definition using '}', but I think inlining might be the better option in the cases seen here, as the other operations used here are pretty small to begin with.
'return' is a macro returning the thread of '^<-', which pushes a value onto the parent stack.

Now that you know about macros and operations, let's define '?'.

Code: [Select]

'? ;[ as '?' is already defined as an immediate operation, we need to quote it. This is done via prefixing the quote character. The quote character is understood by the reader alone and does [i]not[/i] expand into something else like it does in Common Lisp ];
[ <?> & #
  '! & #
]i ;[ this is like ']o', only that it defines an immediate operation ];
I think it should be obvious how this works.

I hope that there is at least one person who can see some merit in this.

[Arzgarb]

Wow, this is eerily similar to an esoteric language called Shift I made a couple of years ago, but never published.

Shift is also a stack-based language whose commands have an immediateness value. The only datatypes are "function" and "blank", the latter of which has only one value which does nothing. The only immediate command is ! (apply), which pops the stack and applies the top element to the rest, or just puts it back if it's a blank. The command even has the same name as yours.

Apparently, the following program prints the infinite string 11111... but I can't currently remember why.

Code: [Select]

@+.!!$.!!+!!
Shift also supports English names for all commands except ! and ? (which pushes a blank), so the above is equivalent to

Code: [Select]

out clone chain!! call chain!! clone!!

Anyway, I'll try to read the full specification of your language when I have more time. It certainly looks interesting.

[Antsan]

Wow, this is eerily similar to an esoteric language called Shift I made a couple of years ago, but never published.

Shift is also a stack-based language whose commands have an immediateness value. The only datatypes are "function" and "blank", the latter of which has only one value which does nothing.

Huh, I have no idea how blank would actually ever be useful but I guess it must have been useful in some way.
Do you have some kind of documentation still lying around?

The only immediate command is ! (apply), which pops the stack and applies the top element to the rest, or just puts it back if it's a blank. The command even has the same name as yours.

It's not a big surprise, at least for me. I think with the concept of immediateness this operation is a must and the name... well, "!" is kinda obvious, especially because this name needs to be short if it should be usable at all.

Apparently, the following program prints the infinite string 11111... but I can't currently remember why.

Code: [Select]

@+.!!$.!!+!!
Shift also supports English names for all commands except ! and ? (which pushes a blank), so the above is equivalent to

Code: [Select]

out clone chain!! call chain!! clone!!

Do you have any idea, what 'chain' does?

Anyway, I'll try to read the full specification of your language when I have more time. It certainly looks interesting.

Yeah, as I already said, currently the specification consists only of what I wrote there in the first post and a table of operations. There are quite a few.


[edit]
The error has been found and eliminated. The complex macro where I suspected the error (actually the most complex operation definition in base.poslin) is actually not the cause of the bug.
[/edit]
I found the next error. Lexical closures currently do not work, but I think this is due to a bug in my poslin code for '}' and not due to a bug in the implementation of poslin itself.

Spoiler: The error - long explanation of the error and of the '{' macro, actually not relevant to the error itself (click to show/hide)

Poslin should support lexical closures and lexical scope in general. That is actually what I implemented the environments for and that's why environments can have parents - those aren't only environments, conceptually they are lexical environments.
Now, a lexical closure is basically a function that uses some variable that is accessible from inside the function, not generally accessible but exists outside the function itself. Or something like that. Maybe you should ask Wikipedia instead of trying to understand what I just wrote.
The standard example for showing lexical closures is the "count" procedure. It gives back successive numbers on successive calls.
In poslin it should be possible to define this function like this:

Code: [Select]

v( n 0 let !
   count
   { n n get 1 + & set
     n get return
   }
)_
'v(' opens a fresh lexical environment for variables.
'n 0 let !' defines a variable in that environment with the value 0.

'n n get 1 + & set' is best understood in two parts.
The inner part is 'n get 1 + &' which retrieves the value of n and adds 1 to that.
The outer part is 'n [inner-part-goes-here] set', which sets the value of the already existing variable n to what the result of the inner part is.
')_' closes the lexical variable environment. If we used ')' in this instance the environment would end up on the stack, which ')_' prevents from happening via throwing that environment away.

The idea is that '}' is called in that lexical variable environment and so the parent environment of the environment that count will use is the lexical variable environment that is opened by 'v(', so if the operation is called it will use it's own environment which has as it's parent the enclosing lexical environment.
Unfortunately the whole thing doesn't work. For some reason the enclosing lexical environment gets lost and when I try to call 'count' I get an error telling me that 'n' is not bound, which means that the environment the operation uses is not correctly set up.

'}' is defined like this:

Code: [Select]

}
[ '] &
  '& &   ;[ The first two lines just close the current stack and convert it into a thread ];
  b* &   ;[ This makes a fresh, unused binding. It's like allocating space, only that I don't need to know how much of it I will actually need and it's going to be garbage collected if I don't use it, thanks to Common Lisp ];
  ~: &   ;[ When I write something into a binding, that binding vanishes from the stack, so if I want to do something with it after setting the binding, I need to duplicate said binding. ];
  r<- &   ;[ Now I move one of the two bindings out of the way onto the return stack - as long as we remove it from there before this operation finishes, everything will be fine ];
  ;[ The strategy is as following: I will now define the actual operation. For this I make a new stack, put the binding that will contain the environment of the operation onto that stack, make sure that environment is loaded,
     when the operation is called and then the thread that was created earlier is inserted, followed by closing the environment of the operation ];
  '[ &
     ^-> &   ;[ Here I insert the binding. That binding is currently empty, but that's not important - the environment will be inserted later.
                The binding will be a literal binding constant in the thread that is created here. ];
     b-> & #   ;[ Now put code to unpack the binding - in this case the environment ];
     ;[ the following three lines are repeated for all the lexical environments. First the environment is duplicated via '~:', then the special environment is extracted via '[envnamehere] e:' and then it is set back in with the last of the three lines
        this is necessary because this way new bindings will be created to hold the environments, so different invocations of the operation will not be able to write into the local environments used by all other invocations ];
     ~: & #
     OP e: & #
     e<-eo & #
     ~: & #
     IMM e: & #
     e<-ei & #
     ~: & #
     VAR e: & #
     e<-ev & #
     ;[ the same is done for the stack in that environment. A literal empty stack can be inserted here ];
     [] ! e<-s & #
     p<- & #   ;[ this will push the environment we just set up onto the path ];
     ^-> &   ;[ This inserts the thread we created earlier ];
     ')_ & #   ;[ And this is the operation to correctly close the environment this operation uses ];
  ']o &   ;[ Now the operation can be defined ];
  ;[ And finally I will need to fill the binding with the environment. It needs to be done after the operation is defined, so the environment that is defined actually contains the operation definition itself ];
  r-> &   ;[ get back the binding from the return stack ];
  e~ &   ;[ get the current environment ];
  e+ &   ;[ make an environment that has the current environment as a parent ];
  eo~ &   ;[ get the current operation environment ];
  e+ &   ;[ make an environment that has the current operation environment as parent ];
  e<-eo &   ;[ set the operation environment ];
  ei~ &   ;[ yadda yadda yadda, the same as with the operation environment with immediateness ];
  e+ &
  e<-ei &
  ev~ &   ;[ and once again with variables... ];
  e+ &
  e<-ev &
  b<- &   ;[ save that environment in the binding and we should be set ];
]i
Yes, it is horrifying. I hope there is a way to figure out what is going on here. I am, of course, wide open to questions.
To help you understand:
The lines which end in '&' are called when '}' is used to define an operation.
The lines which end in '& #' are called when the defined operation is finally called.

If you see anything that makes you think "Well, this might be the culprit", then, by all means, let me know! I have no idea why this isn't working.
I'll also readily give you any definition of any operation you want to know more deeply and supply it with an explanation to the best of my ability.

Spoiler: The error - what the actual bug was and how I fixed it (click to show/hide)

The error lay in the definition of 'v('.
This definition looks a bit strange because it happens before '[' and ']o' are implemented. (Definitions looked even more strange in the beginning, as you can see at the top of base.poslin)
That is why first an empty stack is created and then the threads that are needed to define it are pushed onto this stack, which then is saved into the current operation environment via 'e~<-o', which also ensures that what is defined is converted into a thread.

Code: [Select]

v(
[] !
e~ & <- !
e+ & <- !
e* & <- !
e<-ev & <- !
p<- & <- !
e~<-o !
Assuming '[' and ']o' are implemented, it looks like this:

Code: [Select]

v(
[ e~ &
  e+ &
  e* & ;[ this is a glaring error for which there is only one explanation: I was half asleep when I wrote that line ];
  e<-ev &
  p<- &
]o
You see, this first takes the current environment, makes a child of it and then inserts an empty environment as a variable environment and then proceeds to push the result onto the path.
And if the variable environment is empty, no variable that has been defined earlier can be found.
A minor problem is the 'e+ &'. Creating a child environment of the current environment is actually not necessary, as environments themselves are immutable. This only adds additional indirection, without giving any benefit. The operations 'o(' and 'i(' also had this problem, but not the other fatal one.
The correct version looks like this:

Code: [Select]

v(
[ e~ &
  ev~ &
  e+ &
  e<-ev &
  p<- &
]o
Now a child of the current variable environment is made the new variable environment, which is exactly what 'v(' should do.

[Antsan]

I am now working on a type system for poslin.

To be completely honest, I have almost no idea what I am doing here.
In the ideal case I want type interference to be possible and type checking to be done whenever the user wants. With the evaluation scheme of poslin this means that type checking needs to be doable on stacks and threads.

My idea was to use regular expressions to describe the type of a thread, or rather a pair of regular expressions - one describing the kind of arguments the thread takes from the stack and the kind of objects it leaves.
I hacked together a quick sketch in Haskell for a type checker that does what I imagine.
Here's the code, if you want to play around with it:

Spoiler (click to show/hide)

Code: [Select]

import Data.List

data TypeStack = TypeStack [PoslinType]
               deriving(Show,Eq)

printTypeStack (TypeStack ps) =
  intercalate " " $ map printType $ reverse ps

data TypeOp = TypeOp TypeStack TypeStack
            | TypeError
            deriving(Eq)

instance Show TypeOp where
  show TypeError =
    "TYPE-ERROR"
  show (TypeOp i o) =
    "{ " ++ printTypeStack i ++ " -> " ++ printTypeStack o ++ " }"

data PoslinType = BaseType String
                | Repeated PoslinType
                | Alternative PoslinType PoslinType
                | OpType TypeOp
                deriving(Show,Eq)

printType (BaseType s) =
  s
printType (Repeated t) =
  printType t ++ "*"
printType (Alternative tl tr) =
  printType tl ++ "|" ++ printType tr

(#>) :: TypeStack -> TypeOp -> TypeOp
(TypeStack xs) #> (TypeOp (TypeStack ys) r) =
  TypeOp (TypeStack $ xs ++ ys) r
_ #> _ =
  TypeError

(=~~) :: PoslinType -> PoslinType -> Bool
(BaseType n1) =~~ (BaseType n2) =
  n1 == n2
(Repeated pt1) =~~ (Repeated pt2) =
  pt1 =~~ pt2
pt1 =~~ (Repeated pt2) =
  pt1 =~~ pt2
(Alternative ptl ptr) =~~ a@(Alternative _ _) =
  (ptl =~~ a) && (ptr =~~ a)
pt =~~ (Alternative ptl ptr) =
  ( pt =~~ ptl ) || ( pt =~~ ptr )
pt1 =~~ pt2 =
  pt1 == pt2

(=~) :: TypeStack -> TypeStack -> Bool
(TypeStack []) =~ _ =
  True
(TypeStack (x:xs)) =~ (TypeStack (y:ys)) =
  ( x =~~ y ) && ( (TypeStack xs) =~ (TypeStack ys) )

(~>) :: TypeStack -> TypeOp -> TypeOp
ts@(TypeStack ps) ~> (TypeOp i@(TypeStack is) o)
  | ts =~ i =
    TypeOp (TypeStack $ drop (length ps) is) o
  | otherwise =
    TypeError

check :: TypeStack -> TypeOp
check (TypeStack []) =
  TypeOp (TypeStack []) (TypeStack [])
check (TypeStack [OpType op]) =
  op
check ts@(TypeStack [_]) =
  TypeOp (TypeStack []) ts
check (TypeStack ((OpType (TypeOp i o)):ts)) =
  i #> ( o ~> (check $ TypeStack ts) )
check (TypeStack (t:ts)) =
  (TypeStack [t]) #> (check $ TypeStack ts)

typeOp :: [PoslinType] -> [PoslinType] -> TypeOp
typeOp i o =
  TypeOp (TypeStack i) (TypeStack o)

bt = BaseType
rp = Repeated
(~|~) = Alternative
ot i o = OpType $ typeOp (reverse i) (reverse o)

You can use this to, well, play around a bit. This is, naturally, not available in my poslin implementation but rather a prototype to get an idea how type checking and interference might work.

Now for a bit of... notation or something, I am not quite sure what to call it.
Let's start with something easy.
The type signature of the operation '+' would be:

Code: [Select]

+ :: [ Num Num -> Num ]
- :: [ Num Num -> Num ]
This might look a bit like Haskell code, but this is not the case, as you can easily see if you actually have used Haskell before, so...
It means that '+' takes two objects of type 'Num' from the current stack and puts back an object of the type 'Num'. The same goes for '-'.

Type interference works like this:

Code: [Select]

[ + & - & ] &
 :: check { + - }
   If the type of a non-primary thread is checked, we need to break it down by taking out the front of the thread and doing stuff with it and the type of the back of the thread:
 => in (check {+}) #> out (check {+}) ~> check {-}
   #> is for inserting something to the end of the input type of some operation type, like this: [ A B ] #> [ C -> D ] => [ C A B -> D ]
   ~> checks, whether the first argument "fits" at the back of the input type the second argument. If that is the case, it returns the second argument without everything that has been matched and otherwise it just returns a type error.
 => in [ Num Num -> Num ] #> out [ Num Num -> Num ] ~> [ Num Num -> Num ]
   If the type of a primary thread is checked, just the type of that thread is returned
 => [ Num Num ] #> [ Num ] ~> [ Num Num -> Num ]
   This is trivial - just get the input and output part of the type signature.
 => [ Num Num ] #> [ Num -> Num ]
   The [ Num ] in the call of ~> matches exactly on Num in the input part of [ Num Num -> Num ], so this is valid and returns the thread type signature without that matched Num in the input type
 => [ Num Num Num -> Num ]
   Now insert those two Nums after the input type of the type signature on the right side
An example that shows a bit better how this works with different types:

Code: [Select]

   foo and bar are now assumed to be primary threads with the following type signatures
foo :: A B -> C
bar :: D C -> E

[ foo & bar & ] &
 :: check { foo bar }
 => in (check {foo}) #> out (check {foo}) ~> check {bar}
 => in [ A B -> C ]  #> out [ A B -> C ]  ~> [ D C -> E ]
 => [ A B ]          #> [ C ]             ~> [ D C -> E ]
 => [ A B ]          #> [ D -> E ]
 => [ D A B -> E ]
Here's an example where type checking shows an error:

Code: [Select]

foo  :: A B -> C
bar  :: A B -> D
quux :: C D -> E

[ foo & bar & quux & ] &
 :: [ A B ] #> [ C ] ~> ( check { bar quux } )
 => [ A B ] #> [ C ] ~> ( [ A B ] #> [ D ] ~> [ C D -> E ] )
 => [ A B ] #> [ C ] ~> ( [ A B ] #> [ C -> E ] )
 => [ A B ] #> [ C ] ~> [ C A B -> E ]
   [ C ] cannot be matched to the end of [ C A B ] so a type error is returned. It is important to note that ~> has higher precedence than #>
 => [ A B ] #> type-error
   The result of _ #> type-error is a type error again
 => type-error

Let's go for a more involved example:

Code: [Select]

   A|B means that an object of either type A or B can be taken
   A thread can leave multiple objects on the stack
foo  :: A|B -> B C
bar  :: B C -> B
quux :: A B -> C

[ foo & bar & quux & ] &
 :: [ A|B ] #> [ B C ] ~> ( check { bar quux } )
 => [ A|B ] #> [ B C ] ~> ( [ B C ] #> [ B ] ~> [ A B -> C ] )
 => [ A|B ] #> [ B C ] ~> ( [ B C ] #> [ A -> C ] )
 => [ A|B ] #> [ B C ] ~> [ A B C -> C ]
 => [ A|B ] #> [ A -> C ]
 => [ A A|B -> C ]

Here's an example using repetition:

Code: [Select]

-s :: . Num* -> Num
sort :: . Num* -> . Num*

[ - & sort & -s & ] &
 :: [ Num Num ] #> [ Num ] ~> ( check { sort -s } )
                           => [ . Num* ] #> [ . Num* ] ~> [ . Num* -> Num ]
                           => [ . Num* ] #> [ -> Num ]
 => [ Num Num ] #> [ Num ] ~> [ . Num* -> Num ]
    A* is only removed by a match with A*. It also matches with A, but then it is not removed.
 => [ Num Num ] #> [ . Num* -> Num ]
 => [ . Num* Num Num -> Num ]

That's all I got currently.
Type variables will need to be added. '<?>' for instance would have a type like

Code: [Select]

<?> :: [ Bool A B -> A|B ]

Also matches that might fail are also interesting:

Code: [Select]

foo :: A -> A|B
bar :: B -> C

[ foo & bar & ] &
 :: [ A ] #> [ A|B ] ~> [ B -> C ]
 => [ A ] #> type-error|[ -> C ]
 => type-error|[ A -> C ]
It might be sensible to emit a warning in this case but return [ A -> C ] as the type of the thread.
Another possibility is to make type checking not mandatory but rather provide (immediate?) operations to do the type checking. In this case it is quite possible to let the programmer decide, whether a case such as this should result in a error a warning or nothing when the whole thing is compiled and defined.
I could imagine operation names like '}tr' (tr for "type-check rigid") and '}tw' (for "type-check warn").

I don't know whether this is actually feasible and I also don't know whether this type system is usable.
I don't plan to only use this type system. I actually only want this as a basic one and hope to implement some kind of MOP later, but for that there needs to be some kind of type system already in place, so that is my first attempt.

[Antsan]

After banging my head against this problem for a few days I think that using regular expressions/pairs of regular expressions as types might not be feasible.

First problem: How does one treat the operations 'r<-' and 'r->' which push something onto/pop something off the return stack?
The type of r<-, judging by how it operates if just called, is

Code: [Select]

{ a { a -> b } -> b }|{ a -> a }
This is because, if I put an operation onto the return stack, it is going to be called. If I put something else onto the return stack, the result is going to be just put back onto the current stack. Also, obviously, the type variables 'a' and 'b' here need to be stand-ins for whole regular expressions, not only some basic type.
Now, this is actually not the type of 'r<-', as this is only how it operates if it is not followed by a 'r->' in the same operation on the same level. In that case, it's type is just

Code: [Select]

{ a -> }
Actually it's even more complicated than that, as even if the 'r<-' is not followed by an 'r->' but other operations, then the operation being put onto the return stack will be called on what is on the stack as soon as the current "level" of the operation finishes and will put it's results at that point.
But that can be worked around with special cases. It's not pretty, of course, but still doable, I think.
The type of 'r->' has similar problems or even worse problems, as it depends on what is topmost on the return stack, which can depend on all kinds of stuff I don't know right now.

Another problem: Take an operation that takes a positive integer and then drops that many elements off the current stack.
It's type can be (if it can even be inferred):

Code: [Select]

{ _* Num -> _* }
or maybe

Code: [Select]

{ _* Num -> }
The problem comes when this operation is used elsewhere and another type needs to be inferred:

Code: [Select]

[ 2 ndrop & + & ] &
The type of this should be

Code: [Select]

{ Num Num _ _ -> Num }
but by type interference it's gonna be more along the lines of

Code: [Select]

{ Num Num _* -> Num }|TypeFailure
or something like that. Even if the completely unnecessary warning about a possible TypeFailure is actually not part of what is inferred to be the type then the guaranteed TypeFailure in the following won't be detected:

Code: [Select]

[ 2 3 a b c 2 ndrop & + & ] &
which is, if you ask me, a huge problem.

So... currently I am out of ideas. Probably I'll play around with that type system a bit, maybe try to introduce objects themselves as basic types (as types whose only instances are the objects themselves) and maybe try to get support for natural numbers into the type systems, also having a look at how to handle stuff that interacts not on but also outside the stack (another problem is operations looking something up in an environment - we can guarantee to get back a binding, but we have no way of knowing of what type the object in the binding has).

[Antsan]

Well, after a while I got back into this and now I've got looping.
Witness the implementation of while.

Code: [Select]

o[ |while [] e~<-o !
   eo~ ! |while e-> !
   [ check get call
     [ op get call
       eo~ ! |while e: & call
     ] & #
     when &
   ] &
   b<- !

   'v( & check ~<> & let
         op ~<> & let
         |while &
   ')_ &
]o
It is used like this:

Code: [Select]

next-fib ;[ returns the smallest fibonacci number greater than the given argument ];
{ n arg
  x 0 let
  y 1 let

  [ y x get y get + & x y get let let ] & # ;[ sets x to y and y to x+y; this is called while ];
  [ n get y get > & ] & #                                             ;[ this returns <true> ];
  while &

  y get return
}

While it is quite an achievement for me to finally have while implemented the whole endeavor showed me that there are some serious flaws with how some operations are defined.
Look at the definition of while. Note how I don't just write

Code: [Select]

|while callinstead of

Code: [Select]

eo~ ! |while e: & call
This is due to a very serious flaw in how o[ and ]o are designed.
Remember the definition of }?
One job it had was to make the environments which where present throughout the preceding definition available to the resulting thread. Actually that was it's main job.
]o does no such thing, so the operation environment which is created by o[ is not available when while is called, which again means that the definition of |while is not available, which is why |while cannot just call itself directly but instead the operation environment created by o[ needed to be explicitly put into the thread of |while and the definition then extracted from that on demand (although, now that I think about it, it might be more efficient to get the binding containing the thread of while and obtaining from there on demand).

That is also where this line comes from:

Code: [Select]

|while [] e~<-o !This just sets up the binding for |while in the operation environment.

Now, before I explain the whole definition of while just let me say once again that it is terrifying.

One option to make this better is to change the definition of } so that it gets supplied with a list (which is a stack) of environments to be copied into the thread, so that defining an operation looks something like this:

Code: [Select]

next-fib ;[ returns the smallest fibonacci number greater than the given argument ];
[ STACK VAR ]
{ n arg
  x 0 let
  y 1 let

  [ y x get y get + & x y get let let ] & # ;[ sets x to y and y to x+y; this is called while ];
  [ n get y get > & ] & #                                             ;[ this returns <true> ];
  while &

  y get return
}

Then the definition of while would be

Code: [Select]

while
[ OP VAR ]
{ |while
  [ check get call
    [ op get call
      |while call
    ] & #
    when &
  ]o

  check ~<> & let
  op ~<> & let
  |while &
}
which looks way better.

Although there is still the issue of variable capture.

[Antsan]

If anyone is reading this, write "meep".
Not that the absence of readers is going to convince me to not write here.


I have done a few things since the last post.

The interpreter now includes a stepper. This stepper is activated with 'STEP' and deactivated with 'UNSTEP'. Note that these are words which are directly intercepted by the REPL (exactly like 'QUIT'), so the interpreter never even sees them. If you really want use the symbols of those names for some reason (which I advise you not to do) you'll need to write

Code: [Select]

'STEP
'UNSTEPThe stepper is really very basic. There is no way to step into or out of functions or something like that. Instead, every time before the interpreter does a step, it first prints the program counter, the return stack (this one in reverse order, so the topmost item is at the left) and the current stack. It is quite tedious to use but bug hunting is a lot easier with it.
It also is interesting to see how the interpreter moves through the threads. Makes me appreciate how inefficient my implementations of 'mod', 'fibonacci' and 'factorial' are.

Another primary operator has made it into the language: 'type'. This returns a type object for its argument. Those type objects are all atomic and there is a fixed set of them:

Code: [Select]

·Prim
·ConstantThread
·Thread
·Environment
·EmptyStack
·Stack
·Array
·Binding
·Symbol
·Type
·Comparison
·Boolean
·Nothing
I intend to implement some kind of Meta Object Protocol on top of this – probably after modules/packages are done.


The operations '{' and '}' have been rewritten. While before '{' was something totally static now it is excitingly extensible.
The two are used like this:

Code: [Select]

factorial [ var op ]  ;[ the '[ var op ]' is there to make '{' set stuff up so the resulting operation will use a local variable and operation environment ];
{ n arg~              ;[ arg~ gets and argument from the stack the operation is working on. This is necessary, because 'factorial' doesn't use its own stack. ];
  n get 1 <= &
  [ n get -1 + &
    factorial call
    n get * &
  ]#                  ;[ this is equivalent to '] & #', which is quite commonly seen before '?', 'when' and 'unless' ];
  ?
}

'{' is extensible. That means, if you ever define some kind of namespace for yourself (for instance a namespace for variables with dynamic scope), you can write something like this:

Code: [Select]

var-dyn
[ ;[ insert code for setting up dynamic variable scope here ];
  ;[ the code here should take an environment and describe how to change that environment to produce the desired one ];
]scope
And then use it like this:

Code: [Select]

foo [ var-dyn ]
{ ;[ code ];
}
This mechanism uses the 'SCOPES' slot of the current environment.

Currently 4 'scopes' are defined:

Code: [Select]

op     ;[ lexical operation environment ];
imm    ;[ lexical immediateness environment ];
var    ;[ lexical variable environment ];
stack  ;[ local stack ];


A few operations have been renamed ('e<-o', 'e<-i', 'e<-v' and 'e<-s' and the 'e~' equivalents are the ones affected – an '*' has beend added to the end to signify, that existing bindings in the environment will be overwritten).

The following corresponding operations are planned:
One flavor (with naming scheme 'e<-v') will check for an existing binding and change the value of that binding if it is present, otherwise it will make a new binding.
The next flavor ('e<-v?') will check whether there is an existing binding – if there is, it does nothing, otherwise it makes a new binding – this should be used when I rewrite the standard library again, to make sure that operations which are part of the standard library won't be overwritten by the standard library when they are already defined as primary operations.
The last flavor (not sure what this is going to look like) should only write into already existing bindings and should fail if no binding is present.


A primary operator to make unique symbols is probably necessary to deal with variable/operation/whatever capture.


I guess next up is the generation of unique symbols and then I'll go on to implement the rest of the standard library.
After that is done the standard library should be rewritten (again) to respect operations already defined as primary operations (so everyone who makes his own poslin implementation can provide 'mod' as a primary operation instead of using the slow one in the standard library).
After that… I don't know. Packages and modules maybe?
Another thing that might be necessary is an optimizer that operates on the level of threads. One component should flatten threads as much as possible (thus reducing the workload of the return stack and preparing the thread for other techniques), another one should remove 'r<-' and 'r->' directly after each other (this happens quite a lot – one subthread does some stuff and ends with a 'r->', the next subthread begins with a 'r<-' to get something out of the way) (this only works with the other component). After those two are done, maybe I'll have an idea for other optimizations.

[kytuzian]

meep.

I skim over it when there's a new thing, but haven't read in depth the specification or used the language.

[Orange Wizard]

meep meep

Posting to watch because esoteric languages are cool. I may contribute something later.

[Antsan]

Cool! That's more than I expected.

Today I have no giant post. I finished implementing the promised setting operations and started working on a package system. I'll have to check whether the package system actually makes sense the way I am doing it now, but that's for later.

Also I have uploaded a new binary, which can be downloaded (as usual) here. It's version "0.1.0pr2" and should run on x86 Linux (and probably x86_64 Linux, but I haven't checked).
It now comes with a welcome screen, which looks like this:

Code: [Select]

*******      ****       ****   ****        **** ***  ****
********    ******     **  **  ****        **** ***  ****
 **   ***  ***  ***   **    **  **          **   ***  **
 **    ** ***    *** **    **   **          **   ***  **
 **   *** **      ** ***        **          **   **** **
 *******  **      **  *****     **          **   *******
 ******   **      **    *****   **          **   *******
 **       **      **       ***  **          **   ** ****
 **       ***    ***  **    **  **      **  **   **  ***
 **        ***  ***  **    **   **      **  **   **  ***
****        ******    ******   *********** **** ****  ***
****         ****      ****    *********** **** ****  ***
=========================================================
=========================================================

© 2015 Thomas Bartscher
0.1.0pr2
Forget scope. Then invent it yourself.
where that last sentence is randomly chosen from 4 stupid quotes.
Don't judge me.

Also there is now the operation `e_`, which deletes something from an environment. I am not sure why I didn't include this earlier.

[Antsan]

Here's a fun little thing, if you want to be a polite person:

Code: [Select]

[ ]
> please [ '! & ]i
[ ]
> 1 2 + please
[ 3 ]
>
Or, if you are impatient:

Code: [Select]

[ ]
> NOW! [ '! & ]i
[ ]
> 1 2 +
[ 1 2 + ]
> NOW!
[ 3 ]
>


A new version is available. [Edit]And apparently I forgot to change the version in the welcome message. Not that it makes much sense, anyway…[/Edit]

The types ·Precise and ·Imprecise have been added, which are the two numeric types, the first one being all rational numbers, the second one is for floats.
Also floats are parsed correctly now (instead of being taken to be empty stacks).
A few operations for packages are in the standard library, but they are really very experimental and it is not recommended to use them yet. Unless you want to experiment around yourself, I am happy for any kind of feedback, although there are no comments describing what I actually intend to do.

Ah, what the hell:
The idea for packages comes from Common Lisp, where a package is basically a lookup-table for symbols. If you think back, that is basically what environments in poslin are, only that Common Lisp has a *PACKAGE* variable that tells the reader in which package symbols should be looked up. Also symbols are actually structures in Common Lisp which have a home package, a variable binding, a function binding and probably some other funky stuff whereas in poslin symbols are just tokens without any attributes besides their name at all.
So, with all of that useless knowledge dumped onto you to confuse you, let's go on. The idea is that there should be something like a current package in poslin, where symbols can be looked up. Also there needs to be a storage for packages, so that gives us two new slots: `PACKAGES` (where an environment is saved which maps symbols to packages) and `PACKAGE` (which contains a symbol which denotes the current package). There's all kinds of operations for manipulating these two, but two four others are of greater importance, and they are both immediate: `pk!`, `pk~!`, `pk&` and `pk~&`. They basically do the same thing as `!` and `&`, only that they don't look up stuff in the current environment but in the (current) package and that they only take symbols as parameters. `pk!` and `pk&` also need a package name as additional parameter while `pk~!` and `pk~&` do their lookup in the current package, as you probably already expected.
Currently there is no operation for creating a package (at least not one I'd dare use for the purpose) and I still need an operation (which must be primary) to cut off the parent of an environment (which will probably be named `e-`). Also I am not quite sure on how to do importing and exporting of symbols in packages or how to denote dependencies between packages (if such a thing even is necessary, which it probably is) or how to do loading of multiple packages. Currently packages are only environments which have been stripped of the slots PACKAGES and PACKAGE.


I think of doing a tutorial. I already did one once and that showed how to implement the standard library. The thing is, back then many more operations where primary and thus the first definitions didn't look like this:

Code: [Select]

0 p: ! OP e-> !
0 p: ! OP e-> ! b-> !
e~
b* !
0 p: ! STACK e-> !
0 p: ! STACK e-> ! b-> ! _ !
0 p: ! STACK e-> ! b-> ! _ ! _ ! : ! <- !
b<- !
[] !
0 <- ! p: & <- !
& b<- ! e<- ! b<- !
which even cannot contain any comments, as comments are only implemented quite a bit later.
So, does anyone have any idea for good tutorial material which doesn't need any in- or output besides the REPL?

[Antsan]

I have been writing a tutorial on how to implement structures in poslin.
I am now at the point where structures and their types are almost completely done. Next up are mutable slots for structs (currently any setting operation called on a struct creates a new one).


A little thing about organization.
I plan to have poslin coming in different versions.

The first only contains primary operations, or rather the operations defined in this document: https://bitbucket.org/thomas_bartscher/poslin-specification/src/0f7c09ad5da7a9044cf9df51735049ad92ba9451/spec/prims.txt?at=default
Well, a few operations are missing from this (for example one that returns the length of an array). The basic idea is that this version doesn't load anything externally but is completely bare bones.
That version I call "poslin0". Yeah, it's not very creative.

The second version comes with the standard library, which contains the basic necessities for comfortable working with stacks, defining operations, working with variables, loops…
What it doesn't contain is stuff like packages, a way to define your own data types, modules, type checking, poslin level optimization or anything like that.
It implements the operations in this document: https://bitbucket.org/thomas_bartscher/poslin-specification/src/0f7c09ad5da7a9044cf9df51735049ad92ba9451/spec/base.txt?at=default and would be called "poslin1".
(I think I should get rid of the `fibonacci` and `factorial` operations here.)

If you download the binary distribution, you'll find that it contains a binary file "poslin-dyn" and two scripts, "poslin0" and "poslin1". These two scripts are for starting up the previously described versions.

The third version should contain all the stuff which helps organizing code: Packages, modules and the ability to define your own data types.
Also of interest would be static type checking (if I can come up with something), generic operations and stuff like that.
This would be "poslin2", as you can probably imagine. As the extent of this version isn't quite clear to me there also is no corresponding document right now.

You might wonder why the last two versions are distinct. Well, "poslin1" is relatively small and, more importantly, it is easy to come up with how to do stuff. The stuff in "poslin1" should be uncontroversial. There's no big discussion about how operations should be defined (or at least I am not aware of anything like that) and the same goes for variables, mathematical functions or loops.
The stuff in "poslin2" is not so clear cut. My ideas on how to do object orientation and packages are heavily inspired by Common Lisp which does those things very differently from, say, C++, Java or Haskell for example.
So, everyone who isn't fine with my choice on how to do these things should be encouraged to use poslin1 and implement his own ideas instead of using my implementation of my ideas.
A better idea might be to move all those systems into their own libraries… Hrm…

Poslin0 is distinct from poslin1 for the people who really want to experiment. I don't really know what kind of language you could come up with based on poslin0.
Also poslin0 is kind of a necessity if I ever make that tutorial on how to implement the standard library.


A short while ago I was able to do a slight optimization in the standard library. The optimized operation is `~:`, which duplicates the element on top of the current stack, like this:

Code: [Select]

[ 1 ]
> ~: !
[ 1 1 ]
>
This operation is essential and often used, as it is necessary to duplicate a binding when I want to set its value first and then save the binding in an environment.
Previously it was implemented like this (without the comments and also not with `[` and `]o`, as neither comments nor these operations are available at that moment):

Code: [Select]

~:
[ e~ & STACK e-> &                ;[ … x b<> ];
  e~ & STACK e-> & b-> & _ &      ;[ … x b<> [ … x ] ];
  e~ & STACK e-> & b-> & _ & _ &  ;[ … x b<> [ … x ] [ … x ] ];
  : &
  <- & b<- &
]o
It works like this: It puts the binding of the current stack onto the current stack, then gets the binding again and extracts it's value, which is a stack. This stack is equivalent to the stack we had after we popped off that last binding and before we put back that new value again, so it contains the binding of the current stack on top, which we don't want to have there after duplication, so we drop it from there.
Now we get the value of the current stack again, only that now it contains the binding of the current stack and the stack we made previously, which both need to be dropped so we can take the value we actually want to duplicate from the top of that stack, put it onto the stack before it and finally set the binding of the current stack to the newly constructed stack.
That's a lot of work for just duplicating one value. It's also a lot of unnecessary work.

Take a look at this new version:

Code: [Select]

~:
[ e~ & STACK e-> & b-> &  ;[ … x [ … x ] ];
  : &                     ;[ … x x ];
]o
I don't think this requires much explanation.
Everything runs quite a bit faster now.

Unfortunately swapping the top two elements on the current stack still requires the long route.

[Antsan]

It's been a while.

There now is a repository for poslin libraries I am developing. It will contain only those which are likely to be incorporated into the standard distribution.


I implemented three immediate operations/macros for branching, `]if`, `]when` and `]unless`. They leave the appropriate code on the stack rather than the branches being executed immediately.
They will not replace `?`, `when` and `unless` - I suspect the latter might be useful in some cases while defining macros and stuff.

The respective syntaxes are like this:

Code: [Select]

;[ ]if ];
test & [ then & | else & ]if

;[ ]when ];
test & [ then & ]when

;[ ]unless ];
test & [ else & ]unless


Spoiler: About some deprecated stuff (click to show/hide)

Originally I intended to make the `]if` operation more flexible by also supplying an `if[` (which would have to be used to be able to use `]if` in the first place), so it could be used like this:

Code: [Select]

test & if[ then & | else & ]if
test & if[ then & ]if
This was a huge hassle to implement. It definitely was working, but had the unintended consequence of leaving me with a memory leak (an environment was captured by an anonymous operation in `]if` and thus wouldn't be garbage collected despite never being used again) which I couldn't fix easily and also it just duplicated the functionality of `]when`, which might lead to some undesirable coding styles. Using `]when` should be preferable in any case either way.

Spoiler: Implementation (click to show/hide)

For `]if` we need `|` (did I already show that one?), which just closes the current stack and opens up a new one, like this:

Code: [Select]

|
[ '] &
  '[ &
]i
The task of `]if` is to close the else branch, collect both branches and generate the correct code.

Code: [Select]

]if
[ ']# &
  r<- &
  '& & '# &  ;[ convert the then branch ];
  '[ & ^-> &
       r-> &
       ? #
  ']& &
]i

`]when`

Code: [Select]

]when
[ ']# &
  '[ & ^-> &
       . & # #
       ? #
  ']& &
]i

`]unless` is almost identical to `]when`

Code: [Select]

]unless
[ ']# &
  '[ & . & # #
       ^-> &
       ? #
  ']& &
]i


Dijkstra seemed to think the whole "exceptionally lazy evaluation" scheme had merit:
http://www.cs.utexas.edu/~EWD/ewd00xx/EWD28.PDF
Imagine my enthusiasm when I read that.

Of course his design is quite different from mine, but I still found it neat to see something like this:

[F]rom now on arithmetic operators are primarily treated in exactly the same way as numbers are treated, i.e. the operator word is copied into the stack as well. Everytime [sic] the process of copying has to be interrupted I shall indicate this in the program explicitly by the insertion of a special word, introduced now and represented by "E" (from "Evaluate").

He later goes on to write some simple macros, although he doesn't call them that (which is quite understandable, as the difference, in that draft and poslin alike, is purely by convention and not by implementation).

[Servant Corps]

What types of programs are better suited for a stack-based language like Forth or Poslin? Because I really want to see what you're doing, but if I can't see a practical purpose for it, I can't really feel invested enough to try it.