You are looking at historical revision 3922 of this page. It may differ significantly from its current revision.

Introduction

This extension is an implementation of a simplified dialect of John Backus' FP language. FP can be interpreted directly or translated into Scheme.

Requirements

silex, lalr, readline

Syntax

A program consists of a list of definitions or applications separated by semicolons or periods. The left hand side of a definition specifies a name and the right hand side should be an expression. Here a few sample definitions:

 square = x[id, id].
 add2 = +[id, ~2].

Definitions should be terminated by a separator symbol (either the period (.) or the semicolon (;). Definitions may be followed by a so called where clause, that defines functions that are only visible inside the preceding definitions.

Applications are written as <function> : <object> and can only appear at toplevel.

Identifiers may consist of lowercase letters, digits, an underscore or a single quote and must begin with a lowercase letter. Alternatively any single non-whitespace, non-alphanumeric character that does not have a special meaning can be used as an identifier.

Comments are written as NB. .... Everything following up to the next end-of-line character is ignored.

An expression represents functions to be invoked. FP is a first-order language. One can not define anonymous functions as in lambda calculus. The basic functional operation is composition, designated by simple juxtaposition of functions:

 multiply = show x.   NB. "x" means multiplication

So the function multiply would multiply its arguments and show the result. In lambda-calculus this would be written as

 multiply = \n m.show (n x m)

Note that all functions in FP take one argument and return a single result. Functions that require multiple arguments take them in as a sequence (a list of values).

FP provides a set of functional forms that provide higher order operations on functions:

 /f          "insert"
 \f          "insert-right"
 @f          "apply to all"
 [f, ...]    "construct"
 {f, ...}    "match"
 ~o          "constant"  
 f -> g; h   "conditional"
 while p f   "loop"
 bu f o      "binary-to-unary"
 catch h f   exception handler

insert takes as argument a sequence and inserts the specified function between each element.

apply to all returns a new sequence with the results of applying the function to each element.

construct creates a new sequence with the resuls of calling the function for the given argument.

match takes a sequence as argument and returns either T (true) or F (false), depending on whether each function returns true when applied to the corresponding element. The special pattern # is equivalent to ~T, the pattern ... discards all remaining elements and returns true.

constant ignores its argument and returns the specified object.

conditional applies the first function to its argument and applies the same argument to the second or third function, depending on whether the result is true or false.

loop applies the first function to the argument and if it returns F returns the argument unchanged. If the function returns a true result, then repeat the process with the result of applying the second function to the argument. while could be expressed as an invocation of the following hidden function

 tmp = p -> tmp f; id.

binary-to-unary turns a two-argument function into a function that accepts one argument and has an implicit constant second argument. It is equivalent to

 f [id, ~o]

The catch form allows exception handling: if, during the execution of the second function, an exception occurs, then the first function will be called with the thrown value as its sole argument:

 catch show while ~T throw 123            NB. exits loop and shows value thrown

For convenience, a definition of the form

 name { <pattern> } = <body>.

is equivalent to

 name = { <pattern> } -> <body>; <raise error>.

Further, a bit of syntactic sugar:

 f & g      ==>      f -> g; ~F
 f | g      ==>      f -> ~T; g

Scope

All definitions are global, unless wrapped in where ... end forms. Local definitions are only visible in the toplevel definition that precedes the where clause.

Objects

An object is an atom (a symbol consisting of uppercase characters or _ or a string of characters enclosed by double quotes), a sequence (<x1, ...>), or a number. The atom F is also used as the boolean false value. Any object different from F is considered a true value. An object of the form $<character> results in a number representing the ascii code of <character>. Sequences are tuples of objects of arbitrary length.

Patterns

The match functional allows the two special elements # (named "default") and .... The default atom matches every element (no test is performed) and the dots match all remaining sequence elements.

Builtin functions

 show:x -> x

Prints its argument and returns it unchanged.

 eq:<x, y> -> bool

Return T if x is equal to y, or F otherwise.

 apndl:<x, <y, ...>> -> <x, y, ...>

Prepends x to the front of a sequence.

 apndr:<<x, ...>, y> -> <x, ..., y> 

Appends y to the end of a sequence.

 +:<x, y> -> x + y

Returns the sum of its arguments.

 -:<x, y> -> x - y

Returns the difference of its arguments.

 x:<x, y> -> x * y

Multiplies its arguments.

 %:<x, y> -> x / y

Divides its arguments.

 gt:<x, y> -> bool

Returns T if x is greater than y, or F otherwise.

 lt:<x, y> -> bool

Returns T if x is less than y.

 id:x -> x

Returns its argument unchanged.

 type:x -> atom

Returns one of the atoms ATOM, NUMBER or SEQUENCE, depending on the type of x.

 tl:<x1 x2, ...> -> <x2, ...>

Returns the arguments list with its first element removed.

 null:x -> bool

Returns T if x is the empty sequence.

 length:<x1, ...> -> N

Returns the length of its argument sequence.

 reverse:<x1, ...> -> <..., x1>

Returns the argument sequence reversed.

 cat:<<x1, ...>, <y1, ...>> -> <x1, ..., y1, ...>

Returns a new sequence that is the concatenation of all argument sequences.

 atom:x -> bool

Returns T if x is an atom.

 code:atom -> x

Returns the stored code representation of the global function named atom.

 forget:<a, ...>

Removes stored the code representation of the named functions (the functions themselves are still available). If called with a non-sequence argument, then all stored code representations are removed.

 compile:<a, x> 

Compiles a new global function from the code representation x with the name a.

 load:a

Loads and executes a file containing FP code.

 pack:<n, ...> -> a

Converts a sequence of character codes into an atom.

 unpack:a -> <n, ...>

Converts an atom to a sequence of character codes.

 number:a -> n

Converts an atom into a string, or returns F if the argument can not be converted.

 defined:_ -> <a, ...> 

Returns the names of all globally visible definitions.

 read:n -> <c, ...> 

Read n characters or all remaining (if n is not a number).

 write:x

Write sequence of characters or a single character.

 throw:x

Throw exception, which can be caught by catch.

As a special case an integer number in function position selects the Nth item of a sequence:

 first_and_third = [1, 3]
 first_and_third:<A, B, C, D>          --> <A, C>

Standalone interpreter

A standalone interpreter named fp will be installed that can be used as follows:

 % fp

runs an interactive FP session (interactive mode is also entered if fp is invoked with the -i arguments). Enter Control-D (eof) to terminate the interpreter.

 % fp -c FILENAME

will compile a file named FILENAME containing FP source code into Scheme and write the Scheme translation to stdout.

 % fp -e EXPRESSION

evaluates an FP expression (and furter processes any following arguments).

Any other argument will be treated as a FP source file and loaded/executed.

A compiled version of the standard library (see below) is loaded automatically at startup.

Programming interface

fp-parse

[procedure] (fp-parse PORT-OR-STRING)

Takes FP sourcecode from a string or port and returns an s-expression representation of the parsed code.

fp->scheme

[procedure] (fp->scheme CODE)

Returns a Scheme expression from translating the parsed FP code given in CODE. Evaluating the Scheme expression will run the originally parsed FP program.

Interfacing to Scheme

FP code, when compiled to Scheme can access Scheme functions (and vice versa). FP identifiers are always prefixed with fp:. So for example:

% cat hello.fp
hello = show ~"hello, world!"
hello:#
% fp -c hello.fp
(define fp:hello (lambda (_x) (fp:show ((lambda _ '|Hello, world!|) _x))))

(fp:hello '|#|)

Compiling it is straightforward:

% fp -c hello.fp >hello.scm
% csc hello.scm -R fp2scheme    # to include primitives
% hello

The verbatim form allows inserting Scheme expressions in function or object position:

verbatim "(append '(1 2) '(3 4))"          ==> <1,2,3,4>
secs = verbatim "(current-seconds)"

FP objects map in their natural way to Scheme data and vice versa: sequences are represented as lists, atoms as symbols and numbers are Scheme numbers.

Further notes

To help debugging the functional forms debug and error are provided. They print their argument togther with a user-supplied atom and either continue execution (as in the case of debug) or abort the program (error).

This code is dedicated to John Backus.

Grammar

 program --> toplevel
         --> toplevel separator
         --> toplevel separator program
 
 separator --> "."
           --> ";"
 
 toplevel --> definition ["where" program "end"]
          --> application
          --> verbatim
 
 application --> expression ":" object
 
 definition --> identifier "==" expression
 
 expression --> expr1 "->" expr1 ";" expression
            --> expr1
 
 expr1 --> "while" expr2 expr1
       --> "catch" expr2 expr1
       --> expr2 "&" expr1
       --> expr2 "|" expr1
       --> expr2 expr1
       --> expr
 
 expr2 --> "/" expr2
       --> "\" expr2
       --> "@" expr2
       --> "(" expression ")"
       --> "bu" value object
       --> construction
       --> match
       --> value
 
 value --> number
       --> "~" object
       --> identifier
       --> "debug" atom
       --> "error" atom
       --> "verbatim" atom
 
 construction --> "[" expression "," ... "]"
 
 match --> "{" pattern "," ... "}"
       --> "{" pattern "," ... "," "..." "}"
 
 pattern --> "#"
         --> expression
 
 object --> number
        --> atom
        --> "#"
        --> sequence
        --> "verbatim" atom
        --> "$" character

 sequence --> "<" object "," ... ">"

Examples

NB. stdlib.fp - Standard library

zero = eq[id, ~0].
succ = +[id, ~1].
pred = -[id, ~1].
heads = @1.
tails = @tl.
not = id -> ~F; ~T.

trans = null 1 -> []; apndl[heads, trans tails].
compress = cat @listify trans.
listify = 1 -> tl; [].
make = zero 1 -> []; apndl[2, make [pred 1, 2]].
distl = trans[buildl, 2].
buildl = make[length 2, 1].
distr = trans[1, buildr].
buildr = make[length 1, 2].
and = null -> ~T; not 1 -> ~F; and tl.
or = null -> ~F; 1 -> 1; or tl.
e = or @eq distl.
count = /+ @(eq -> ~1; ~2) distl.
flatten = atom -> id; atom 1 -> apndl[1, flatten tl]; cat[flatten 1, flatten tl].
take = null 2 -> []; zero 1 -> []; apndl[1 2, take[pred 1, tl 2]].
drop = null 2 -> []; zero 1 -> 2; drop[pred 1, tl 2].
pair = atom -> ~F; eq[length, ~2].
ge = eq -> ~T; gt.
le = eq -> ~T; lt.
iota = zero -> []; apndr[iota pred, id].
NB. tak.fp - the venerable "tak" benchmark
NB. run as "fp tak.fp"

tak = not lt[2, 1] -> 3; 
      tak[tak[pred 1, 2, 3], 
	  tak[pred 2, 3, 1],
	  tak[pred 3, 1, 2]].

tak:<18, 12, 6>
NB. palindrome.fp
 
palindrome=/and @eq trans[id, reverse] cleanup unpack where
cleanup=compress[@letter, id] @lowercase.
letter=bu ge $a & bu le $z.
lowercase=(bu ge $A) & (bu le $Z) -> bu + 32; id
end.
 
show palindrome:"A man, a plan, a canal - Panama!".
show palindrome:"able was I, ere I saw elba.".

References

[1] "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" John Backus, Communications of the ACM, Aug. 78, Vol. 21, Num. 8

Authors

felix winkelmann

License

Copyright (c) 2007, Felix L. Winkelmann
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

 Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer. 
 Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the 
   documentation and/or other materials provided with the distribution. 
 Neither the name of the author nor the names of its contributors
   may be used to endorse or promote products derived from this
   software without specific prior written permission. 

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Version History

2.0
complete re-write, many simplifications and enhancements
1.1
Added some builtin functions, extended atom syntax
0.1
initial release