Outdated egg!

This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for the CHICKEN 4 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

fp

Introduction

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]

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 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.

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.

 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.

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).

 % 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.

Programming interface

fp-parse

[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.

fp->scheme

[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.

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
          --> 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 "," ... ">"

Examples

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.".

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.1: pattern bindings, bugfixes, extended selectors, removed tl
2.0: complete re-write, many simplifications and enhancements
1.1: Added some builtin functions, extended atom syntax
0.1: initial release