The Heresy Programming Language
John S. Berry III
Abstract
The Heresy language is a functional Lisp/Scheme dialect implemented in Racket, with syntax inspired by the BASIC family of programming languages. It’s principle goals are to provide a simple core language for BASIC and other programmers to experiment with and learn how to program functionally. This document will detail the general philosophy of the Heresy language, such as exists, as well as the language syntax and functions.
The Heresy language was created by John S. Berry III with additional contributions from many others in the Racket community.
Heresy and this documentation are Copyright (c) 2014 John S. Berry III and released under the terms of the GNU LGPL.
1 The Heresy Rules
The Heresy language is developed according to a few basic "ground rules," which the author and contributors attempt to follow in developing new features and functions for the language. These are as follows:
-
Heresy is BASIC - Heresy is inspired by BASIC, and aims to be at least somewhat easy for BASIC programmers to learn. Mostly this means we prefer BASIC names for functions over the Lisp name, and naming conventions like the $ for string functions.
-
Heresy is a Lisp - Heresy is still a Lisp, and loves simple syntax and s-expressions. While it makes use of some sugaring like literal keywords for certain common primitives, these are best used sparingly. Heresy is the Diet Coke of Evil, just one calorie, not quite evil enough.
-
Heresy is functional - Functional, but not Haskell. It is not intended solely as a vehicle for absolute functional purity. I love Haskell. You love Haskell. We don’t need to write another Haskell. Think more in terms of a lower-calorie, more intelligible Clojure.
-
Heresy is for learning - Heresy started as a learning project, a chance to learn how Lisp and functional programming really work on a practical level. I hope that, in time, it can be that for others as well, especially those who grew up with BASIC like myself and still sometimes struggle to get their head around the functional style. In particular, this means the Heresy-written portions of the source are generally written in as clear a manner as possible, as they are intended to be self-teaching.
-
Heresy is an experiment - Heresy is an experimental language. It’s very DNA is as a mad idea that came to life, and it’s development should be ready and willing to embrace new mad ideas and run with them. This is where carry came from, and I hope to have more mad ideas in the future.
-
Heresy is for everyone - As a statement of culture, the Heresy community welcomes the contribution of all people, who taste equally delicious to the jaws of mighty Cthulhu. No discrimination, harassment, or any other mistreatment of contributors on the basis of age, race, sexuality, or gender will ever be tolerated by myself or anyone else who wishes to be part of this project.
2 Heresy Syntax and Conventions
Generally speaking, Heresy follows standard s-expression syntax as expected from any Lisp, being composed of parenthesized sequences of terms in Polish notation. Each sequence thus begins with an operator or function, and any number of arguments or additional s-expressions as needed.
There are however a few exceptions to usual expectations in the case of certain special forms like for, def, and if. These make use of additional literal terms as part of their syntax, to provide more clarity and similarity to BASIC-style syntax.
In accordance with that goal, Heresy also follows certain naming conventions as a matter of style. Functions which produce a string value are appended with $, and in general where a naming conflict between two similar functions in Racket/Scheme and BASIC exists, prefer BASIC.
When borrowing BASIC syntax and naming for use in Heresy, the author has generally relied chiefly on QBASIC and ECMA BASIC for reference.
3 Heresy Reference
3.1 Declarations
(def name value)
Defines a new variable of name with the given value.
(def fn name ([arg ...]) body ...)
Defines a function of name, which when called evaluates its body expressions with the given list of arguments bound to local variables for use in the body of the function’s definition. Note that there are a number of additional options here for defining arguments. Default values can be ascribed to an argument by enclosing it in additional parentheses:
> (define foo (x (y 1)) (+ x y))
> (foo 3 4)
7
> (foo 5)
6
Two patterns as well exist for taking an arbitrary number of values. The argument names list can be forgone entirely and substituted with a single name (generally args* by convention), which will then contain a list of any and all values passed to the function. The second method is the use of the dot (.) in the body of the arguments list followed by a single variable (usually called rest).
(let ((name value) ...) body ...)
Binds the given name-value pairs for use in the local context created by the body of the expression. This is used to define local variables, such as are needed within a function. Note that local functions can potentially be assigned this way by storing anonymous functions, but there is a built-in syntax for defining a single such function, like so:
(let proc ((name value) ...) body ...)
When let is called this way, it defines a local function proc (conventionally called recur), which can then be called from within the body of the let in order to perform local recursion; the name-value pairs thus act as arguments to the function proc.
(fn ([arg ...]) body ...)
Creates an anonymous function with the given arguments, that evaluates its body when called. This is the lambda expression from other Lisps and functional languages, and a given fn can be passed as a value (as can named functions, for that matter) wherever called for. An anonymous function can also be evaluated directly in place by using it as the operator in an expression, like so:
> ((fn (x y) (* x y)) 4 5)
20
3.2 Conditionals and Loops
(if test then texpr else fexpr)
Evalutes test and, if test is True, evaluates texpr, otherwise it evaluates fexpr. Note that only a single expression can be placed in each “slot” in the syntax; if you need to do multiple things, use a do block.
(select (test1 expr1) ... [(else fexpr)])
Given a list of test-expression pairs, evaluates the tests in order until it finds one which is True, and evaluates the matching expression. The else expression is always true: if an else is found at the end of the select statement, its matching fexpr will be evaluated. If no test in select is true, returns #<void>.
(select case texpr ((val ...) rexpr) ... [(else fexpr)])
Evaluates texpr and compares it to vals in turn until it finds a value that is eq? to the result of texpr. If one is found, it evaluates the matching rexpr. Like with select, else is always considered True, and will therefore always evaluate its fexpr. If no matching val is found, select case evaluates to #<void>. Not also that the (val ...) is a list, and can contain as many values as is needed, such as in the following example:
> (select case (* 2 3)
((2 3 4) (print "Nope."))
((5 6 7) (print "Yup."))
(else (print "something is horribly wrong.")))
Yup.
(for (var in list [with cry]) body ...)
Iterates over list evaluating it’s body with the head of list assigned to var, then recurs with the tail of list until it returns Null. for loops declare an implicit variable cry which can be passed a value with carry. They may also be interrupted with break. See below for more details.
(do body ...)
Evaluates its body in order, returning the result of the final body expression.
(do loop [with cry] body ...)
Evaluates body repeatedly until a break statement is encountered. Declares the implicit variable cry, which can be reassigned with the carry operator.
(break [value])
Breaks the continuation of a for or do loop evaluation. If provided a value, returns that value as the result of the loop.
(carry value)
When called in the body of a for or do loop expression, immediately begins the next iteration of the loop, and passes the given value to the implicit variable cry.
cry
Loops declare an internal variable called cry, which defaults to Null, and which is passed automatically to the next iteration of the loop, and is returned when the loop concludes. The value of cry can be specified at the beginning of the loop with the optional with parameter, and carry can be used to pass a new value of cry to the next iteration.
3.3 Predicates and Logic
(list? v)
Returns True if v is a list.
(null? v)
Returns True if v is Null, where Null is defined as the empty list ’().
(zero? v)
Returns True if v = 0.
(one? v)
Returns True if v = 1.
(eq? x y)
Returns True if x and y are the same object.
(equal? x y)
Returns True if x and y are equal.
(symbol? v)
Returns True if v is a symbol: ie. a quoted name such as ’foo. See quote in 3.4.
(atom? v)
Returns True if v is an atom: ie. a number, symbol, or procedure, rather than another list or Null.
(lat? l)
Returns True if l is a list composed solely of atoms.
(and expr ...)
Returns True only if all given expressions are True.
(or expr ...)
Returns True if any given expression is True.
(not v)
Returns True if v is False, else returns False.
else
A special keyword for True, used as a literal in conditional statements.
True
The boolean truth value. Actually an alias for #t in the Racket implementation. Note that, in Heresy, as in Racket, anything not explicitly False is considered True.
False
The boolean false value. Actually an alias for #f in the Racket implementation.
Null
An alias for the empty list ’().
3.4 Syntax and Evaluation
(quote v)
’v
“Quotes” the given v, without evaluating it’s contents. A quoted list is passed merely as data, a quoted atom is a “symbol” as per symbol?. Can be shortened to ’.
(quasiquote v)
‘v
Same as quote, but can be “escaped” with the unquote and unquote-splicing syntax. Can be shortened to ‘.
(unquote v)
,v
When encountered within a a quasiquoted block, evaluates v and quotes its value instead. Can be shortened to ,.
(unquote-splicing v)
,@v
Similar to unquote, but splices the result of evaluating v in place. Can be shortened to ,@.
(error [symbol] message)
Halts the program, returning an error of symbol: message where symbol is a quoted value (customarily the name of the current function) and message is a string.
(run form)
Evaluates the given form. Usage is not recommended.
(rem any ...)
Ignores its arguments and returns void. Useful for block comments.
(def macro name ([pattern ...]) template ...)
Defines a new macro with name. A macro can best be thought of as a function which is not evaluated, but rather returns syntax to be evaluated in the form of a template. Each name described in the pattern defines a “pattern variable” which can then be used in the body of the template and will pass any syntax contained in that portion of the pattern in the appropriate location matched in the template. The elipsis ... can be used in a pattern to indicate repeatable values.
(apply fun v ... lst)
Applies fun to the given arguments, as if it had been called with (fun v ... lst).
3.5 Input and Output
(print [&|lit] [v])
Prints the given v to the current output, or stdout if not otherwise specified, followed by a newline. (print & v) outputs without a newline, while (print lit v) outputs as a literal form that can be directly read back by (input stx ...) as code. A bare (print) merely prints a newline to the current output.
(? ...)
A shortened macro for print.
(input [stx] [string])
Reads a line of input from the current input, or stdin if not otherwise specified, and returns the value read as a string. (input stx ...) instead reads a value using the standard reader, thus providing syntax which can be evaluated with run. If additionally provided with a string, this will be output as a prompt to the current output.
(using io-port body ...)
Evaluates the body, with input/ouptut redirected to the given io-port. Only the file port is supported at this time.
(file name as mode)
Opens the file name as the new target for input or output, depending on the mode provided. mode is a symbol, of one of the following:
’output Opens file as the current output port. Will fail if file already exists.
’rewrite Opens file as the current output port, rewriting its contents if the file exists.
’input Opens file as the current input port.
(list v ...)
Returns a list containing the given values.
(join a b)
Joins a and b into a pair. If b is Null, a list is created containing a. If b is a list, a is joined to the head of the list.
(head l)
Returns the head (first element) of the list l.
(tail l)
Returns the remainder of list l after the head. If the list has only one element, returns Null.
(range start to finish [step n])
Generates a list of numbers, incrementing from start to finish by n. If no n is provided, defaults to 1. Note that, unlike BASIC’s for x = y to z, descending sequences where start is greater than finish can only be declared by including a negative n. Otherwise only Null will be returned.
(map fun l)
Given a single-argument function fun, returns a list with fun applied to each item in l.
(filter fun l)
Given a predicate fun, returns a new list containing only those elements of l for which fun returns True.
(len l)
Returns the number of items in l.
(foldr fun base l)
Given a function fun with two arguments, returns the cumulative result of fun being applied to consecutive pairs, starting from base and the rightmost element of l.
(foldl fun base l)
Similar to foldr, except that it combines pairs from the left, starting with the head of l and base.
(reverse l)
Returns a list with the order of l reversed.
(index n l)
Returns the nth entry of l, indexed from 1.
(index* l dims ...)
Walks through nested lists according to the given dims, essentially finding index recursively for an arbitrary number of dimensions. For example, given a nested list three lists deep, (index* l 2 3 1) would return the 1st element of the third element of the 2nd lst, like so:
> (def dave ’(1 (2 3 (4 5)) 6))
> (index* dave 2 3 1)
4
(inlst item l)
Searches l for item, returning the index of item if found, or False if not.
(left l n)
Returns a list of the leftmost n elements of l.
(right l n)
Returns a list of the rightmost n elements of l.
(mid l idx n)
Returns n entries of l starting from index idx.
(slice l first [last])
Returns a slice of l, starting at first and ending at last. If last is not provided, it defaults to the end of the list.
(append1 l1 l2)
Returns a list with l2 appended to the end of l1.
(append l ...)
Returns a list of the given ls appended together in order.
(assoc tgt l)
Searches the heads of a list of lists l and returns the first matching list or False.
(subst tgt new l)
Searches the heads of a list of lists l, and if it finds tgt, returns a new list with the tail of tgt substituted for new. Otherwise, returns False.
(heads l)
Returns a list of the heads of a list of lists.
(sort fun l)
Sorts list l according to the comparison function fun.
(zip l1 l2)
Returns a new list of lists combining l1 and l2. Excess length of either list is dropped.
(zipwith fun l1 l2)
Returns a new list, combining the matching pairs of each list with fun. Excess length of either list is dropped.
3.7 Strings
(=$ x y)
Returns True if the two strings are equal.
(& str ...)
Concatenates its arguments into a single string.
(list$ str)
Returns a list of one-character strings from the given string.
(str$ n)
Converts a number n to a string.
(empty$? str)
Returns True if the string is empty (“”).
(len$ str)
Returns the length of the string, indexed from 1.
(list& l)
Given a list of strings, returns a single concatenated string.
(head$ str)
Returns the head (first character) of the string.
(tail$ str)
Returns the tail (remaining characters) of the string, unless str is empty, in which case it returns the empty string.
(left$ str n)
Returns a string of the leftmost n characters of str.
(right$ str n)
Returns a string of the rightmost n characters of str.
(mid$ str idx len)
Returns a section of str, len characters long, beginning at idx.
(slice$ str start [finish])
Returns a slice of str beginning at start and ending at finish. If not specified, finish defaults to the length of the string.
(instr str search)
Returns the index of the first instance of search in str, or False if not found.
(split str [delimiters])
Returns a list of string sections split at the given delimiters. If delimiters is not specified, defaults to space (“ “).
(+ [x y ...])
Adds the given numbers left to right and returns the result. If only one argument is given, returns the argument. If no arguments are provided, returns 0.
(- x [y ...])
Subtracts the given numbers left to right and returns the result. If only one argument is given, returns (- 0 x).
(/ x [y ...])
Divides the numbers from left to right and returns the result. If only one argument is given, returns (/ 1 x).
(* [x y ...])
Multiplies the numbers given from left to right and returns the result. If no argument is given, returns one. If one argument is given, returns the argument.
(= x y ...)
Returns True if all the numbers are numerically equal.
(< x y ...)
Returns True if all arguments are greater than the one previous going right (ie, x < y < z, etc.)
(> x y ...)
Returns True if all arguments are less than the one previous going right (ie, x > y > z, etc.)
pi
A bound variable containing the 64-bit floating point value of pi.
e
A bound variable containing the 64-bit floating point value of Euler’s number.
(mod x y)
Returns the modulus of x divided by y.
(abs n)
Returns the absolute value of n.
(even? n)
Returns True if n is even.
(odd? n)
Returns True if n is odd.
(sgn n)
Returns -1 if n is negative, 0 if n is zero, and 1 if n is positive.
(inc n)
Returns the value of (+ n 1).
(dec n)
Returns the value of (- n 1).
(exp x)
Returns the value of ex.
(sin x)
Returns the sine of x as a floating point value.
(cos x)
Returns the cosine of x as a floating point value.
(tan x)
Returns the tangent of x as a floating point value.
3.9 Random Numbers
Heresy’s random number generator operates slightly differently to traditional BASIC’s, in order to offer a more functional approach. Rather than defining a single global seed which the RND function then refers to, Heresy’s randomize returns a “generator” function with a given seed, allowing one to name and seed as many generators as one needs, though for practical purposes a default RND is still provided which is automatically created and seeded with a derivation of the current time in milliseconds..
(randomize [seed])
Returns a new generator function initialized with seed. If no seed is provided, defaults to timer.
(rnd)
A pre-defined generator which returns a random number between 0 and 1, exclusive, seeded by timer.
timer
A special internal variable which contains the current time in milliseconds.
Things are Heresy’s definable data structures. Unlike the objects of most object-oriented languages, which often exist to hold and carry mutable state and actions with which to change that state, Things are immutable. A Thing, once sprung to life, cannot itself be altered, but can be called with the correct syntax to return a new Thing with different internal values for its internal data fields.
Things are essentially functions, lambdas specifically, with predefined syntax arguments. They are first class values, and can be passed freely just as any other data, but can also be passed arguments to either return the values of their fields, return a new Thing, or to employ any functions contained within the thing.
(describe Name (field value) ...)
Defines a new type of Thing, given Name. By convention, Things are generally named in uppercase, though this is not required by the syntax. Each field is an internal name and external symbol, which is mapped to the given value. Anonymous functions (fn) can be assigned as values to Thing fields, and those functions can access the fields of the Thing by name.
({Name} [’symbol|’fields|pattern])
Once a Thing has been described or bound to a name by other means, that Name is bound locally as a function, and can thus be called with special syntax to return its contents or to return a new copied Thing. In more detail, these syntaxes are as follows:
(Name)
Returns an association list containing the contents of the Thing, ie. a list in the form of: ’((field value) ...)
(Name ’fields)
Returns a list of symbols for the fields contained within the Thing. Note that the symbol ’fields takes precedent over the field names within, in order to prevent overwriting this syntax.
(Name ’symbol)
Returns the value of the field associated with ’symbol, the quoted form of the field name described when the Thing type was first declared. Will return an error if no such named field is found. If the value associated with symbol is a function, this expression can be used as the operating function of a further expression like so:
> (describe Lord-Cthulhu (eat (fn (x) (print (& "Devours " x)))))
> ((Lord-Cthulhu ’eat) "Dave")
Devours Dave
(Name pattern)
pattern = ’([*|value] ...)
Returns a copy of the Thing, with new values according to the pattern passed to the original Thing. Pattern must be a quoted list of either *’s or values, in order according to the fields of the Thing as originally defined (so the first *|value matches the first field, the second to the second field, and so on). A * in a field indicates that the value is copied in-tact, while a value becomes the new value of the field in that position. For example:
> (describe Santa (size ’fat)
(sleigh ’ready)
(sack ’full))
> (describe Santa-after-Christmas (Santa ’(* * ’empty)))
> (Santa-after-Christmas)
((size ’fat) (sleigh ’ready) (sack ’empty))
(send Thing ’symbol args ...)
An alternate syntax for accessing functions within Things, send calls the function named by (Thing ’symbol) with the given arguments and returns the result.
(Self ...)
Self is the self-referring identifier for a Thing, allowing for functions within Things to call the Thing itself. Note that if it is only the values of the other fields, this is not necessary, as fields are defined as local names within the context of the Thing, and thus can be referred to simply by name.
(Y fn)
The strict Y fixed-point combinator. Allows for recursion of anonymous functions. Given a fn1 which contains a single named argument, and within which is an additional single-argument fn2, the innermost fn2 can call the named argument of fn1 as if it were a function name in order to recur on itself. For example, the factorial function can be defined thusly, using the Y-combinator:
(define Fact
(Y
(fn (fact)
(fn (n)
(if (zero? n)
then 1
else (* n (fact (- n 1))))))))
Note however that usage of the Y-combinator for recursion is not especially efficient, and the more traditional recursive approach is generally recommended whenever possible (which is most of the time).
(partial fun args ...)
Returns a function with args partially applied to fun, which can then be passed the remaining arguments, as many as needed to complete the calculation. For example:
> (map (partial + 2) (range 1 to 4))
(3 4 5 6)
(compose fn1 fn2)
Returns a new function which is a composition of fn1 and fn2. This function evaluates fn2 with its arguments, and then applies fn1 to the result of fn2.
> (define abs-sub (compose abs -))
> (abs-sub 4 5)
1