/01    10\/11    20\/21    30\/31    40\/41    50\/51    60\/61    70\/71    80\
|--------||--------||--------||--------||--------||--------||--------||--------|

Programming Language Apocalypse #00014
Author: Clifford Wolf <http://www.clifford.at/>
Date: 2009-11-12

          Yet another LISP dialect for numeric and CAS applications
          *********************************************************

This document describes a LISP-like programming language for pocket calculators
and computer algebra systems.

The design goals have been:

 *  To overcome some of the imo less comforting aspects of LISP by adding some
    syntacic suggar, such as the [..] notation from Scheme and reducing the
    trailing ')' hells by introducing the '|' notation that allows for e.g.
    "(not | is-nan | first x)" instead of "(not (is-nan (first x)))".

 *  To ease the implementation of the VM on a wide range of hardware platforms.
    E.g. be leaving out the more complex VM features found in some of the 'big'
    LISP dialects.

 *  To optimize the language for mixed numeric and CAS applications. E.g. by
    handling undefined identifiers as self-referencing identifiers and so
    minimizing the gap between an evaluateable term and an algebraic expression.


Main differences to existing LISP dialects such as Common LISP:
===============================================================

A more formal definition of the language can be found in the rest of this
document. but for starters I'd like to point out the main differences between
this language and existing LISP dialects:

 *  Undefined identifiers are handled as self-referencing identifiers.
    Arithmetic expressions do not fail on such arguments but the term is
    expanded as far as possible and instead of a concrete value a (possibly
    simpler) term is returned (see example at the end of this document).

    This should help closing the gap between numeric and algebraic
    computations.

 *  In addition to NIL there are the values TRUE and FALSE for boolean values.
    This is needed because the expression (< A (+ 3 5)) might evaluate to
    something like (< A 8) which is different from NIL but nevertheless not
    automatically true.

 *  There is no (let ...) statement. Instead there is a (local ...) statement
    for declaring a block with local variables and within that statement
    the functions (def ...) and (undef ...) can be used to define and undefine
    local variables.

    This has two advantages: First it allows for easy mixing of code and
    variable definitions without the need to cascade many (let ...) statements
    and second it eases reusing one algebraic expression with different
    variables beeing defined and not defined without the need to change
    the variable quoting within the algebraic expression.

 *  The only difference between a list and a function is that the function also
    has an assoziation with a parent context for the lexical variable lookup.

    Arguments are passed using a special variable and may be transfered to local
    variables using the (args 'arg1 'arg2 ...) command. The argument list is not
    part of the formal function declaration.

    It is even possible to use a simple list like a function, in which case the
    list is evaluated as function with a dynamic scope.

    This also means that there is only one common namespace for functions and for
    data variables.

 *  In addition to lists and atoms this language also has a primitive type
    for low-level (hash based) dictionaries. They are needed for the containers
    for local variables anyways and by making this feature accessable from the
    language we also get support for plain dictionaries but also for namespaces.

 *  This LISP dialect is case sensitive and all unicode characters are allowed
    as identifiers. This allows e.g. the use of greek letters or combining
    characters in mathematical expressions.


Extensions to basic S-Expressions:
==================================

  [...]     may be used instead of  (...)
  (A | B)   is a shortcut for       (A (B))
  'xyz      is a shortcut for       (quote xyz)
  #n(...)   is a shortcut for       (function '(...))


Variable scoping and resolution:
================================

  - Normal variables are using lexical scoping

  - Variables starting with '$' are lisp-like special variables

  - Identifiers starting with ':' are always self-referencing

  - Unkown identifiers are self-referencing by default


Primitive functions:
====================

  (def identifier value)
     defines and sets a variable in the most inner (local ...) block

  (undef identifier)
     removes a variable definition from the most inner (local ...) block.

  (set identifier value)
     sets a previously defined variable to a new value
     produce a runtime error if the variable is not defined

  (args argnames...)
     define all N argnames and assign the N first elements from $$ to this
     variables. $$ itself is reset to point to the remaining elements of $$.

  (local expressions...)
     container for local variables, evaluates all expressions
     and returns the value of the last one

  (namespace expressions...)
     like (local ...) but returns the dictionary holding the local variables.

  (group expressions...)
     evaluates all expressions and returns the value of the last one

  (loop expressions...)
     evaluates all expressions in an endless loop

  (block label expressions...)
     evaluates all expressions and returns the value of the last one

  (return label value)
     terminate the specified block and return the value
     the label is optional - when it is ommited the most
     inner while loop is terminated

  (first value), (rest value), (nth n value)
     lisp-like list access primitives
     unlike in lisp, nth starts counting with 1

  (cons first rest), (quote value), (list values...)
     lisp-like list generation primitives

  (if cond then else)
     if cond is equal TRUE, "then" is evaluated, if it is equal
     to FALSE, "else" is evaluated. If cond is neighter TRUE nor
     FALSE a runtime error is produced. The "else" branch is optional.

  (function list)
     Convert the given list to a function with the current local block
     as its parent context.

  (eval expr)
     Evaluate expression. (actually: evaluate it twice.. - otherwise
     this would be equivialent to a [group ...] statement)

  (parse string)
     Parse a string and return the s-expression, or return NIL on
     parser errors.

  (read prompt)
     Display the prompt and read a line from input.

  (print expr)
     Print out the value of the expression.


Special variables:
==================

  Special variables (variables starting with a '$') are global variables.
  They can be set as any other normal variable using (set ...) and
  (def ...), but when (def ...) is used they are automatically reset to
  their previous value when the current local block is left or they
  are undefined using the (undef ...) statement.


Functions and evaluation algorithm:
===================================

  Evaluation of an expression E is done using the following algorithm:

    if E is a list or function:
      FUNC = evaluation of first list element of E
      if FUNC is a list or function:
        - push current value of '$$' on the stack
        - create new '$$' list variable
        - evaluate all further elements of E and append results to '$$'
        RET = evaluation of FUNC
        - restore old value of '$$' by popping it from the stack
        - result of evaluation is RET. end.
      else:
        - handle E as builtin function or generate runtime error. end.
    else (E is not a list or function):
      if E is an resolveable identifier:
        - result of evaluation is the resolved identifier. end.
      else:
        - result of evaluation is the atom itself. end.

  The only difference between functions and lists is that functions
  have their own context pointers (closures) and simple lists don't.


Primitive data types:
=====================

  Number types:

    [+-]?[0-9]+
      Integer with bigint support

    {Integer}/{Integer}
      Rationale number

    [+-]?([0-9]+\.[0-9]*|[+-]?\.[0-9]+)
    [+-]?([0-9]*\.)?[0-9]+e[+-]?[0-9]+
      Floating point number

    {Number}i
      Imaginary number

  Boolean types:

    TRUE, FALSE
      The two boolean values

  Strings (utf8):

    "[^"]+"
      Some kind of yet not defined backslash escaping notation allows the
      use of all unicode characters even in a 7bit ascii source file. 

    """\n?(.*?)\n?"""
      Multi-line-string. Different notation but same atom type.

  Identifiers:

    ([UTF8]|[a-zA-Z!@$%^&*_=/?<>~])([UTF8]|[a-zA-Z!@#$%^&*_=/?<>~.0-9+-])*
      I.e. almost everything else is an identifier
      (The placeholder [UTF8] matches all chars that are not in 7bit ascii)
      The backslash notation can be used to type untypeable characters.
      Dots are special and indicate a dictionary lookup. This way it is
      possible to implement namespaces.

  Dictionaries:

    { KEY VALUE ... }

  Lists:

    ( A . B )

  Functions:

    #<parent-context-number>( .. code .. )
      When generating a function atom the context number is ignored
      and the current local block is used parent context. Unless when
      evaluating the function it behaves exactly like a list.

  Nothing:

    NIL
      Used e.g. to terminate lists.


Functions for operating on primitive data types:
================================================

  +, -, *, **, /, %
    Arithmetic operations
    When called with non-numerical arguments the term is
    simplified as much as possible and then returned as result.

  <, <=, ==, !=, >, >=
    Relational operations (returns TRUE or FALSE)
    When called with non-numerical arguments the term is
    simplified as much as possible and then returned as result.

  not, and, or, xor
    Relational operations (returns TRUE or FALSE)
    When called with non-boolean arguments the term is
    simplified as much as possible and then returned as result.

  (max values), (min values), (abs value), (floor value), (ceiling value),
  (sin value), (cos value), (asin value), (acos value), ...
    The usual math functions.

  (str-cat string1 string2 ...)
    Concatenate strings

  (str-slice string1 first num)
    Returns a "num" chars long segment of the string starting with the char
    number "first". The first char has the index 1.

  (str-length string)
    Returns the number of (utf8) chars in the string.

  (str-chr number ...)
    Convert unicode character codes to a string.

  (str-ord string)
    Convert a string to a list of integers containing the
    unicode character codes.

  (is-number value)
  (is-complex value)
  (is-boolean value)
  (is-string value)
  (is-id value)
  (is-nil value)
  (is-atom value)
  (is-dict value)
  (is-list value)
  (is-function value)
    Returns TRUE or FALSE depending on the type of the argument.
    (An atom is everything that is not a dict, list or function)

  (is-defined identifier)
    Returns TRUE if the identifier is defined and FALSE otherwise.

  (eq value1 value2)
    The ultimate test function as known from lisp
    (might not do what you'd expect on lists and dictionaries.)

  (dict-keys dict)
  (dict-has dict key)
  (dict-del dict key)
  (dict-set dict key value)
    Manage dictionaries


Examples:
=========

  a function that generates accumulators. i.e. a function that
  takes a number n, and returns a function that takes another
  number i and returns n incremented by i.

    (def 'foo #|local
      (args 'n)
      #[set 'n (+ n (first $$))]
    )

  a function that calculates the biggest prime factor of its argument.

    (def 'mpf #|local
      (args 'n)
      (def 'x [floor (** n 1/2)])
      (loop
        (if (= x 1) [return n])
        (if (= [% n x] 0) [return (max (mpf x) (mpf (/ n x)))])
        (set 'x (- x 1))
      )
    )

  two functions in a namespace:

    (def 'my-name-space |namespace
      (def 'foo NIL)
      (def 'set-foo #|set 'foo |first $$)
      (def 'print-foo #|print foo)
    )

    (my-name-space.set-foo "Hello World!")
    (my-name-space.print-foo)

  interactive example using hypothetical 'alg-parse' and 'alg-isolate'
  algebra functions.

    => (is-defined 'a)
    %1: FALSE

    => (alg-parse "a + 100 = 15 * 20")
    %2: (= (+ a 100) (* 15 20))

    => (eval %2)
    %3: (= (+ a 100) 300)
    
    => (alg-isolate %3 a)
    %4: (- 300 100)

    => (eval %4)
    %5: 200

    => (def 'a %5)
    %6: 200

    => (eval %2)
    %7: TRUE