You are looking at historical revision 3746 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
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 represenation x with the name a.
load:a
Loads and executes a file containing FP code.
pack:<n, ...> -> a
Converts a sequence of character coes 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
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