Adds the sin function, over a radial frequency value as a primitive to
the language. As usual, the user provides a length and the signal
repeats over the given length.
Adds the exponential signal as a primitive. Given some base constant,
computes the base raised to the sample index at each sample value. Like
all other signals, it is periodic with a pre-determined length.
Adds the unit ramp signal, defined as t for all times t, as a primitive
to the language. Like all other signals, it cycles with a given period
value determined by signal length.
Adds the unit step signal as a primitive of the language. The unit step
is defined to be 0.0 at time 0, and 1.0 otherwise. As with other
signals, users have to window the signal, which is otherwise infinite.
Previously, we didn't handle the case in which the user passed no
arguments, since getArgs returns only the program name in this case. We
now handle that case and simply fire up the repl on the starting context
when no file is provided.
Implements signal advance and delay under a unified shift function.
Since all our signals are viewed as periodic shift amounts are always
interpreted in a periodic context, and support automatic wraparound.
In order to support this we have to encode the length of a signal, so
we've added that to the signal representation. This means that certain
infinite signals (delta) are no longer infinite, but this makes more
sense for the discrete domain regardless.
Generates the unit impulse function which cycles infinitely and has a
value of 1.0 only at time 0. The remaining values are all 0.
This also fixes a bug in the Evaluator whereby we couldn't define
primitives that took no arguments.
The environment now holds bindings instead of raw forms. A binding is
currently just a form with additional information, in this case,
documentation, but we may expand this further later.
This commit adds a useful feature: an anamorphism primitive for defining
signals. Given a starting value and a function, we can produce new
signal values:
(~> (fn [x] (+ 1.0 x)) 0.0)
Will produce the signal of all the natural numbers, beginning with zero.
By windowing this signal users can get some computed snapshot of the
values.
Supporting this feature easily required making signals proper
sexpressions, not atoms, so that we can leverage the existing evaluator
to compute the signal values. However, there are still some kinks to
work out. For example, one currently has to evaluate the result of a
window to force computation of the signal expressions, but this is a
start.
Window takes natural numbers and a signal and produces a window over the
signal values given by the numeric arguments, inclusive of the first and
exclusive of the second. For example:
(window 0 2 (~ 1.0 2.0 3.0 4.0 5.0))
=> (1 2)
In addition, we'll use conventional commit messages from now onwards.
Adds a new kind of atom, signals, and a primitive for constructing them.
Signals are potentially infinite streams of doubles. By default, their
values are repeated upon complete consumption of the stream.
Defines a new type of REPL pass that allows us to evaluate forms under
different execution contexts. This should make it easier to swap between
typing and evaluation passes and eventually sequence them.
After this, the lexer will recognize and distinguish doubles (values
with decimal place) from integers. We also provide a type for such
values. This is part of the way toward usefully representing signals as
a primitive.
Adds an initial implementation of the type checker, which is a separate
compiler pass from evaluation. We use the lambda calculus again, but
this time we run it over a context full of typings for each form, where
the literal program s-expressions are codified into representations of
their types.
There is no inference. Users can annotate types using (type <name> <type
form>) where type form performs special conversions from type names like
int to their representations.
I've had to make the lambda calculus into an interface to permit us to
use it to operate on a typing context. In general this will be our
approach to implementing various compiler passes.
Previously, all primitives were binary functions, which was somewhat
limiting, particularly when it comes to defining structs of various
length. This commit reworks the implementation of primitives to take the
more general list of s-expressions as an argument, allowing us to define
an arbitrary number of struct (tuple) fields.
I've also changed the evaluation of primitive arguments to ignore
side-effects. We evaluate all arguments before calling a primitive, but
any side effects of said arguments are currently ignored. We may want to
restore this behavior, though.
We can represent tuples of values in the lambda calculus, in general,
using the form:
(fn [f] ((((f x) y) z) ...))
where `f` is another function that accesses a component of the struct by
returning an argument:
e.g. second: (fn [x y] y)
(fn [f] ((f x) y))
(((fn [x y] y) a) b) {apply second}
((fn [y] y) b) {apply to a}
(b) {apply to b}
We can use this as a basis for user-defined types.
The repl can now read in entire programs, handling imports appropriately
(sort of -- the entire content of imports will still wind up in the
global scope at the end, really we want imports in a given file to be in
scope privately *only* while evaluating that file; otherwise they should
not be transitively imported).
Declaring a file a that depends on b now works. Note that the repl does
not support invoking against a set of files just yet.
The REPL (and eventual compiler) now supports importing forms from
another file. This is a special case, since we don't want to complicate
the evaluator. Because of this, the repl needs to recognize import
forms.
At present, there are two ways to import:
(as [<name> (import <file>) ...])
and
(import <file>)
All imported forms must be qualified and separated by a colon `foo:bar`.
When the as form is used, the import qualifier is bound to a given name.
When the import form is used in isolation, the filename is used as
the qualifier (right now it includes the extension).
This is a slight convenience that makes it a little bit easier to work
with the main sourcefile tree since we don't have bunch of ibc
files clogging up the directory.
With this change, the repl/evaluator now supports binding names to
values using a def form. We also endeavor to lookup the values of bound
names when encountered and carry context mutations across repl states.
This slightly tweaks our approach to environments. Additionally, it
introduces an execution context, which keeps track of different scopes
(which each have an environment) throughout the course of a program's
execution.
We define a basic interface for managing definitions in the programming
environment. This will permit users defining their own functions and
other forms.
`letrec` bindings may refer to themselves in their bodies. We achieve
this by replacing all binding values in a letrec form with an
application of the Y combinator to express the recursion. Since we don't
evaluate eagerly, it's important to note that for simple values the form
will yield an anonymous function awaiting subsequent evaluation.
This new form permits definitions such as:
(letrec [f (fn [n] (if (= n 0) 1 (* n (f (- n 1)))))] (f 3))
=> 6
I've also added a special pattern syntax for this form.
Let transformations are not dependent on evaluation. Since they are part
of the enriched lambda calculus, it makes sense to define them in
Lambda.
This commit also breaks out a number of utility transformations on
s-expressions into the Util module, which makes our definitions of let
transformations more concise.
In addition to re-implementing the Y combinator as a primitive (and
eliminating another special case in the evaluator), this commit adds a
function for making Unary primitive functions, which need to be handled
slightly differently than binary primitives (namely, they do not return
a partial function on a unary argument).
Reimplementing alpha as a primitive allows us to remove a special case
from the Evaluator, simplifying it.
In the process of implementing alpha as a primitive, I caught a bug in
the implementation of partial functions for primitives, which is also
fixed here. We'll also need to implement separate primitive creation
functions for unary and binary primitives after this change.
This commit makes our implementation of primitives much dryer by
leveraging a lambda expression. Primitives are now binary function as
well, and typically expect two atoms as arguments (expecting unary
primitives, which will expect Nil). This simplifies the passing of
arguments to primitives, since we decompose expressions beforehand.
This commit adds an evalPrim function to clean up our handling of the
evaluation of primitives. Additionally, it makes various improvements to
the handling of a few forms.
This evaluator, equipped with Y and equality, can compute the factorial
of a number:
(let [f (fn [fac n] (if (= n 0) 1 (* n (fac (- n 1)))))] ((Y f) 3))
=> 6
Let bindings are only valid if they contain an even number of forms:
[x 1 y 2] (ok) [x] (not ok) [x 1 y] (not ok)
This commit fixes a small bug whereby valid forms were sometimes
misidentified as erroneous.
This commit implements basic equality on atoms as a primitive of the
language. Two atoms are equivalent precisely when their internal
representations are equivalent.
Sometimes, it can be a bit difficult to debug evaluated expressions when
they're printed in the normal fashion. This commit adds a `showDebug`
function that prints expressions tagged with corresponding internal data
structures, for example,
(a b nil)
becomes:
(<Expression> <atom>a (<Expression> <atom>b <Nil>))
under `showDebug`.
The Y combinator allows us to express recursion in the lambda calculus
without relying on recursion itself. This isn't an appropriate place to
delve into the complete background, but the gist of the combinator is
that it applies a function to itself. Internally, this may be expressed
as a simple reduction rule:
Y H -> H (Y H)
Which is precisely the approach we take in this implementation. We use Y
to support direct recursion in the rose language.
Alpha conversion renames bound terms in lambda abstractions to prevent
collisions between variables in nested abstraction contexts.
Alpha conversion is a prerequisite to supporting recursion in the lambda
calculus, otherwise the Y combinator can replace bindings incorrectly on
application and lead to unintentional infinite loops.
This initial implementation of alpha is naive and can probably be
improved. Aside from the ugly code repetition, there are quite a few
list and data s-expression traversals here that can likely be fused
using a fold.
Let expressions allow users to define local bindings. Let expressions in
Rose follow the classic lisp form:
(let (bindings) body)
Where bindings must be an even number of names and values, and body is
an evaluable function body. Let expressions are transformed into an
anonymous function application that applies the values in the `bindings`
form to the variables in `bindings`. Since let expressions may occur in
large contexts, such as function bodies, they can cause name
collisions/shadowing. For now, we don't perform any renaming or
collision detection.
Originally, the evaluator was defined by pattern matching on top level
arguments to a call to `evaluate`. However, the only discriminant in
`evaluate` at the moment is the form being evaluated, and the top-level
patten matching code was a bit difficult to read.
This commit refactors evaluate into a series of mutually recursive
functions, one specialized to each form of input. The `go` function
handles matching on forms and dispatching to the appropriate function.
Technically, if is implementable in pure lambda calculus equipped with
boolean reductions. For convenience, however, I've defined if as a
special case in the evaluator.
Scott Olsen
fool