peg-0.1: README.md

Peg Programming Language
========================

Overview
--------

Peg is a lazy non-deterministic concatenative programming language.

In contrast to most concatenative programming languages, Peg starts evaluation from the right, evaluating arguments to the left as needed.

For example, even though the word 'no' can never be resolved:

    no 1 2 + --> no 3

This is because `+` requires only two arguments on the stack.

Branching is accomplished with the choice operator `\/`. Both paths are followed non-deterministically.  Paths are terminated when a word cannot be resolved.

Multiple definitions for a word cause the definitions to be substituted non-deterministically.  This allows words (even built-in words) to be extended for new types.

For example, to extend `sqrt` to operate on the word `Four`:

    [Four eq? Two swap assert] "sqrt" :def

A word can only be resolved if the word can operate on its arguments.  The built-in words `assert` and `deny` can only be resolved on the arguments `True` and `False` respectively.  `ifte` is provided as part of the library.

    [ 1 ] 2 \/ popr --> [ ] 1

The basic types are integers, floats, characters, words, and stacks.  As with the top level stack, these stacks are evaluated lazily.  Stacks are 'live', and will be evaluated as demanded, by such words as `popr`.  There is no way to directly extract an item from the left, and there is no way to extract an item without evaluation.

    [1 2 3 +] popr --> [1] 5

Peg is flat, in that any expression can be divided on white space (except inside a literal), the pieces evaluated independently, and when the results are concatenated, evaluate to an equivalent expression to the original expression.

Example:

    [ 1 2 + ] popr --> [ ] 3
    [ 1 2 +        --> [ 3
    ] popr         --> ] popr
    [ 3 ] popr     --> [ ] 3

Built-in words
--------------

The format below is:

`input stack` `word` --> `output stack` \/ `alternate output stack` -- notes

--------------------------------

`x` `pop` --> 

`x` `y` `swap` --> `y` `x`

`x` `dup` --> `x` `x`

`[` `xn` .. `x0` `]` --> `[xn .. x0]` -- gathers stack items into a list until `[` if possible

`[ .. ]` `x` `pushr` --> `[ .. x]`

`[ .. x]` `popr` --> `[ .. ]` `x` -- forces evaluation of `x`

`[ .. x]` `[y ..]` `.` --> `[ .. x y .. ]` -- concatenates stacks without evaluating anything

`[ .. ]` `dupnull?` --> `[ .. ]` (`True` \/ `False`) -- indicates if the stack is empty, works on partial stacks

`True` `assert` --> -- only resolves if the argument is `True`

`False` `deny` --> -- opposite of assert

`x` `y` `\/` --> 'x' \/ 'y' -- continues execution non-deterministically with `x` and `y`

`int?`, `float?`, `word?`, `list?`, `char?`, `string?` -- test type of argument, returning `True` or `False`
 
`x` `y` `eq?` --> `True` \/ `False` -- is `x` a primitive type (non-stack) equal to `y` (also not a stack)

`[ .. ]` `"word-name"` `:def` --> -- define the word `word-name` to be equivalent to the stack argument

`"word-name"` `:undef` --> -- undefine the word `word-name`

`[ .. ]` `$` --> ` .. ` -- append stack argument to upper level stack and execute

`x` `y` `seq` --> `x` `y` -- force evaluation of `x`

`x` `show` --> `"x"` -- convert `x` into string representation

`"x"` `read` --> `x` -- convert string representation of `x` into `x`, opposite of `show`

`+`, `-`, `*`, `div`, `^`, `^^`, `**`, `exp`, `sqrt`, `log`, `logBase`, `sin`, `tan`, `cos`, `asin`, `atan`, `acos`, `sinh`, `tanh`, `cosh`, `asinh`, `atanh`, `acosh`, `<`, `<=`, `>`, `>=` -- numeric and comparison words defined as in Haskell Prelude

Library: lib.peg
----------------

Most words are based on the Haskell Prelude, some stack combinators are taken from Joy.

`foldr` and `foldl` are swapped from the Haskell definitions, because "lists" are stacks, and elements are added to the right side of a stack.  Similarly for `scanr` and `scanl`.

Most of the Haskell Prelude is implemented, except words that aren't very useful or are replaced by a built-in word.  I'm still working on IO.