fp
Note: This is taken from the Chicken Wiki, where a more recent version could be available.
This extension is an implementation of a simplified dialect of John Backus' FP language. FP can be interpreted directly or translated into Scheme.
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 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
_ "bottom"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. A pattern can be preceded by a binding declaration of the form ID=. This creates a temporary local function named ID that can be used in place of the numerical selector that would normally be used to access the sequence element at that position, so for example:
swap{x=number, y=number}=[y,x]. NB. accept two numbers and swap their position.A pattern binding of the form ID=# can be abbreviated to ID=.
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>.A definition of the form
(name) = ...
represents a memoizing function: after the first invocation, the result is saved and will be returned on any subsequent invocation (regardless of the argument value).
A toplevel expression of the form
<ATOM, ...>
will load and execute the files named by ATOM, ... as if they were directly included in the currently compiled/executed program.
bottom ignores its argument and signals an error.
Further, a bit of syntactic sugar:
f & g ==> f -> g; ~F f | g ==> (1 -> 1; g 2) [f, id] `O ==> bu eq O *f ==> apndl[f 1, -1]
All definitions are global, unless wrapped in where ... end forms. Local definitions are only visible in the toplevel definition that precedes the where clause.
An object is an atom (a symbol consisting of letters or _ and beginning with an uppercase letter 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.
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.
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.
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 the stored 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.
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 the next line of input (if n is the atom LINE) or all remaining (if n is not a number).
write:x -> x
Write sequence of characters or a single character.
writef:<a, <c, ...>>
Writes a string to a given file.
readf:a -> <c, ...>
Reads the contents of a file returning a sequence of character codes.
existsf:a -> bool
Returns a boolean indicating whether a file with the given name exists.
statf:a -> <n, ...>
Returns a 13-element sequence with the following contents: inode-number, permissions, number of hard links, uid of owner, gid of owner, size, access-, change- and modification-time, device id, device type, blocksize and blocks allocated.
system:a
Executes a shell command and throws an error if the exit status is non-zero.
readp:a -> <c, ...>
Executes shell command and return output as a string.
writep:<a, <c, ...>>
Executes shell command feeding it second argument as input.
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, or the Nth tail of a sequence, if negative:
first_and_third = [1, 3] first_and_third:<A, B, C, D> --> <A, C>
As a special case, the selector 0 always returns the empty sequence.
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).
% fp -t ...
will enable trace mode by instrumenting the generated code with trace output code.
% fp -m ...
will invoke a user-defined function called main after all files have been processed with a sequence holding any command-line arguments. The result should be an integer which will be treate as the exit status of the program.
Arguments following -- will be ignored.
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.
[procedure] (fp-parse PORT-OR-STRING)
Takes FP sourcecode from a string or port and returns a list of s-expressions representating each toplevel form of the parsed code.
[procedure] (fp->scheme CODE [TRACE])
Returns a Scheme expression from translating the parsed FP code given in CODE. Evaluating the Scheme expression will run the originally parsed FP program. if TRACE is given and true, then the generated Scheme code will be instrumented to display function entry- and exit messages to stdout.
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.
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.
program --> toplevel
--> toplevel separator
--> toplevel separator program
separator --> "."
--> ";"
toplevel --> definition ["where" program "end"]
--> application
--> sequence
--> verbatim
application --> expression ":" object
definition --> head "==" expression
head --> "(" id ")"
--> id
expression --> expr1 "->" expr1 ";" expression
--> expr1
expr1 --> "while" expr2 expr1
--> "catch" expr2 expr1
--> expr2 "&" expr1
--> expr2 "|" expr1
--> expr2 expr1
--> expr2
expr2 --> "/" expr2
--> "\" expr2
--> "@" expr2
--> "*" expr2
--> "(" expression ")"
--> "bu" value object
--> construction
--> match
--> value
value --> number
--> "~" object
--> "`" object
--> identifier
--> "debug" atom
--> "error" atom
--> "verbatim" atom
construction --> "[" expression "," ... "]"
match --> "{" pattern "," ... "}"
--> "{" pattern "," ... "," "..." "}"
pattern --> identifier "=" pattern
--> identifier "="
--> "#"
--> expression
object --> number
--> atom
--> "#"
--> sequence
--> "verbatim" atom
--> "$" character
sequence --> "<" object "," ... ">"NB. stdlib.fp - Standard library zero = `0. succ = +[id, ~1]. pred = -[id, ~1]. heads = @1. tails = @-1. not = id -> ~F; ~T. trans = null 1 -> []; apndl[heads, trans tails]. compress = cat @listify trans where listify = 1 -> -1; [] end. make = zero 1 -> []; apndl[2, make [pred 1, 2]]. distl = trans[buildl, 2] where buildl = make[length 2, 1] end. distr = trans[1, buildr] where buildr = make[length 1, 2] end. and = null -> ~T; not 1 -> ~F; and -1. or = null -> ~F; 1 -> 1; or -1. count = /+ @(eq -> ~1; ~2) distl. flatten = atom -> id; atom 1 -> apndl[1, flatten -1]; cat[flatten 1, flatten -1]. take = null 2 -> []; zero 1 -> []; apndl[1 2, take[pred 1, -1 2]]. drop = null 2 -> []; zero 1 -> 2; drop[pred 1, -1 2]. pair = atom -> ~F; eq[length, ~2]. ge = eq | gt. le = eq | lt. iota = zero -> []; apndr[iota pred, id]. member = null 2 -> ~F; eq[1, 1 2] -> ~T; member[1, -1 2]. merge = pack cat @unpack. n2a = pack unpack.
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.".
[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
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.