I-Script

Author: Jeff Dalton

Introduction

I-Script is a programming language that can be used in I-X applications. It can be used to define functions that can be called in compute conditions and may acquire other uses in the future.

A number of different representations of I-Script code are available:

Core Abstract Syntax and Semantics

Environments and Evaluation

A binding pairs an identifier with a location that contains a value. The identifier is said to be "bound to" the location. Sometimes the word "variable" is used to refer to an indentifier, but it can also used to refer to a binding.

A location can contain different values at different times. When the value changes, the new value is said to be "stored in" or "into" the location. It is assumed that it is always possible to obtain new locations that are different from each other and from any existing ones.

A value can be any object.

An environment is a collection of bindings. An environment can be extended by adding a new set of bindings. This creates a new environment rather than modifying the existing one. In the extended environment, the new bindings take precedence over any earlier bindings, in the environment, for the same identifiers.

The basic unit in I-Script is an expression. Expressions are said to be "evaluated" to produce a value. Another way to say that is to say "the value of" some expression or type of expression "is" and then to describe the value, referring to parts of the expression as needed.

Evaluation takes place with respect to a lexical enviromnent and a global environment. An expression is always evaluated "in" a lexical environment, and the evaluation process can also make use of the global environment.

The core semantics for I-Script is given in terms of an abstract syntax for expressions. For each kind of expression, there is a description of how such expressions are evaluated. Implementations are not required to work in exactly that way, but they must produde the same values and have the same side-effects in the same order.

Expressions may contain other expressions, and the evaluation rules are recursive. An outermost, or "top-level" expression is evaluated in an empty lexical environment. Evaluation rules may specify a different lexical ennironment for their subexpressions, and that applies only to those subexpressions.

True and False

There are distinguished values true and false that correspond to Boolean.TRUE and Boolean.FALSE, respectively, in Java. However, most values are considered true. We will therefore typically use "a true value" and "a false value" to refer to the two cases.

Abstract Syntax

The abstract syntax of an expression type is given as follows:

class-name:
   [element | attribute] field-name: value-class-name
   ...
The element-attribute difference, and the field names, are relevant when expressions are written as XML or in a similar concrete form. They are sometimes ignored when giving the semantics.

Literals

literal:
   element value: object
The value of a literal is the indicated object.

Variable References

var-ref:
   attribute name: name

The name is considered an identifier. If the lexical environment contains a binding for that name, the value of the var-ref is the value stored in the location bound to the name in that enviromnent. Otherwise, the global environment is considered instead. If neither environment contains a binding for the name, an exception is thrown.

The global environment contains a number of predefined names. TRUE is bound to a location containing true, and FALSE is bound to a location containing false. The values of other predefined names are described in the section on built-in functions.

Functions and Function Calls

call:
   element function: expression
   element arguments: list of expression

The function expression is evaluated to produce a function, then the argument expressions are evaluated in order. Finally, the function is applied to the arguments, and the result of that application becomes the value of the call.

There are two kinds of functions, built-in functions and closures. A closure is obtained by evaluating a lambda-expression.

Sequential Evaluation

sequence:
   element of: list of expression
The expressions in the sequence are evaluated in order and the value of the last expressin becomes the values of the sequence. If there are no expressions in the sequence, the value is unspecified.

Conditional Forms

if:
   element test: expression
   element if-true: expression
   element if-false: expression
The test expression is evaluated. If the result was a true value, then the if-true expression is evaluated, and its value becomes the value of the if; otherwise the if-false expression is evaluated, and its value becomes the value of the if.
and:
   element of: list of expression
If there are no expressions, the value of the and is true. Otherwise, the expressions are evaluated in order. If one of the expressions returns a false value, the remaining expressions are not evaluated, and that false value becomes the value of the and. If, instead, all of the expressions return true values, the value of the last expression becomes the value of the and.
or:
   element of: list of expression
If there are no expressions, the value of the or is false. Otherwise, the expressions are evaluated in order. If one of the expressions returns a true value, the remaining expressions are not evaluated, and that true value becomes the value of the or. If, instead, all of the expressions return false values, the value of the last expression becomes the value of the or.

Assignments and Definitions

assignment:
   attribute to: name
   element value: expression

The name is regarded as an identifier. The expression is evaluated to produce a value. A location is then obtained as follows:

  1. If the name is bound in the lexical environment, use the location in that binding; otherwise:
  2. If the name is bound in the global enviromnet, use the location in that binding; otherwise:
  3. Create a new location, bind the name to that location in the global environment; and use that new location. (This is the only time that an environment is modified.)
Finally, the value of the expression is stored in the chosen location and becomes the value of the assignment.

Lambda-Expressions

lambda:
   element parameters: list of name
   element in: expression

The value of a lambda is a function that "captures" the lexical enviromnent as it is when the lambda was evaluated and, when applied to arguments, extends that environment with bindings that bind each parameter to the positionally corresponding argument, resulting in a new environment, e; the expression in the lambda is then evaluated in e, and the resulting value becomes the value of the application of the lambda.

The function produced by evaluating a lambda is sometimes called a (lexical) "closure", because it "closes over" a (lexical) environment.

Local Variables

let:
   element bindings: list of binding
   element in: expression

binding:
   attribute name: name
   element value: expression
The expressions in the bindings are evaluated in order. The lexical environment is extended by binding each name to the value obtained from the corresponding expression to create a new environment, e. The expression in the let is evaluated in e and the resulting value becomes the value of the let.

Iteration

while:
   element test: expression
   element repeat: expression
The value of a while is obtained by repeatedly evaluating the test expression, then the repeat expression, stopping as soon as the value of the test expression is false. The value of the while is then the most receently obtained value of the repeat expression. If the repeat expression was never evaluated (because the test returned a false value when it was first evaluated), then the value of the while is unspecified.

Predefined Names

Note that names that are all capitals, such as TRUE, are intended to be constants and should never be assigned new values. Some interpreters will prevent such assignments, but others may not.
TRUE -> a true value
FALSE -> a false value
(identity object) -> object
Returns the same object.
(apply function object ... list) -> object
Applies the function to arguments obtained by taking all of the objects before the last (which must be a list), followed by the elements of the list, then returns the result of that application. apply is thus a way to expand a list into individual arguments to a function, as well as to place some other individual arguments before the ones from the list.
(error object ...)
Throws an exception of class Interpreter.Error with a message formed by concatenating string representations of the objects.

Predicates

(symbolp object) -> boolean
Returns true if the object is a symbol and false otherwise.
(numberp object) -> boolean
Returns true if the object is a number and false otherwise.
(stringp object) -> boolean
Returns true if the object is a string and false otherwise.
(listp object) -> boolean
Returns true if the object is an llist and false otherwise.
(consp object) -> boolean
Returns true if the object is a cons (a non-empty llist) and false otherwise.
(not object) -> boolean
Returns true if the object is a false value and false if the object is a true value.
(eq object object) -> boolean
Returns true if the objects are the very same, identical object (i.e., if they are not really two separate objects at all), and false otherwise.
(equal object object) -> boolean

Returns true if the objects are structurally equal and false otherwise.

(The meaning of "structurally equal" needs to be specified.)

Lists

(null object) -> boolean
(cons object llist) -> llist
(car llist) -> object)
(cdr llist) -> object)
(first llist) -> object)
(rest llist) -> object)
(list object ...) -> llist
(make-list collection) -> llist
(mapcar function llist) -> llist

Sequences

A sequence is a collection, a string, or an Object[] array.
(empty sequence) -> boolean
Returns true if th sequence is empty and false otherwise.
(length sequence) -> long
Returns the number of elements in the sequence.
(elt sequence long) -> object
Returns the indicted, 0-origin, element of the sequence.

Collections

(make-collection type collection) -> collection
Returns a new collection with contents taken from an existing collection. The type is a symbol and must be one of list, set, or sorted-set.
(contains collection object) -> boolean
(add collection object) -> boolean
(remove collection object) -> boolean
(for-each function colletion) -> colletion
(map function colletion) -> llist

Hash Tables

(make-hash-map) -> hash-map
(make-context-hash-map) -> context-layered-hash-map
(get map key default-value) -> value
(put map key value) -> value
(for-each-entry function map) -> map

Numeric Functions

(= number number) -> boolean
(/= number number) -> boolean
(< number number) -> boolean
(> number number) -> boolean
(<= number number) -> boolean
(>= number number) -> boolean
(+ number ...) -> number
(- number number) -> number
(* number ...) -> number
(/ number number) -> number
(% number number) -> number
These functions perform the corresponding comparisons or arithmetic operations. % is the mod or remainder operator. Numbers must be longs or double precision floating point numbers (doubles). The numbers are processed in the order in which they appear as arguments, and the arithmetic result is a long if all of the numbers are longs; otherwise, any partial result is converted to a double when the first double is encountered, any remaining calculations are performed as double precision floating point, and a double is returned as the final result.
(ceiling number) -> long
(floor number) -> long
(truncate number) -> long
(round number) -> long
PI -> pi

(sin number) -> double
(cos number) -> double
(tan number) -> double
(asin number) -> double
(acos number) -> double
(atan number) -> double
(atan2 number number) -> double
(to-radians number) -> double
(to-degrees number) -> double

(sqrt number) -> double

I/O

At present, there is only simple I/O using Java's System.in and System.out.
(print object ...) -> unspecified
Outputs a string representation of each object without any added whitespace.
(println object ...) -> unspecified
Outputs a string representation of each object without any added whitespece except for a newline sequence at the end.
(read) -> object
Reads characters until it ontains the representation of an object, then constructs and returns the corresponding object.

Java Utilities

(find-java-class symbol-or-string) -> class or false
Returns the class that has the specified name, or else a false value if no such class can be found. The fully qualified class name should be used. For example:
    (find-java-class "java.util.LinkedList")
(java-call object method-name argument ...) -> value
Does the equivalent of
    object.method-name(argument, ...)
except that the run-time classes of the object and arguments are used. The most specific applicable method is called, where "most specific" is as defined in the Java Language Specification, section 15.11.

The object can be any object; it can be a class to call static methods. The method-name must be a symbol or string. The reserved method name new can be used with a class as the object to call a constructor. If the Java method returns null, a unique object that represents null is returned instead. That object is available as the value of the constant JAVA-NULL.

There's automatic conversion between primitive values (such as ints) and their corresponding wrapper objects (such as Integers). However, it's important to remember that I-Script numbers correspond to Java Longs and Doubles, while some Java methods what something else, typically an int. To get an int from a Long, call it's intValue method, like this:

    (java-call 12 "intValue")
The result will be an int that is automatically converted to an Integer, which allows it to match int parameters in method signatures. Such Integers cannot be treated as numbers in other ways. They can't, for example, be added.

JAVA-NULL -> the object that represents null

Syntax: Quick Reference

Lisp Syntax

expression ::= literal | var-ref | call 
            |  if | cond | and | or
            |  assignment | definition
            |  lambda | let | let*
	    |  sequence | while

literal ::= (quote data) | 'data

var-ref ::= symbol

call ::= (function argument*)
function ::= expression
argument ::= expression

if ::=  (if test if-true if-false)
test ::= expression
if-true ::= expression
if-false ::= expression

cond ::= (cond cond-clause*)
cond-clause ::= (test if-true*)

and ::= (and expression*)

or ::= (or expression*)

assignment ::= (setq var-ref expression)

definition ::= define | defun

define ::= (define var-ref expression)

defun ::= (defun function-name (variable*) expression*)
function-name ::= var-ref
variable ::= symbol

lambda ::= (lambda (variable*) expression*)

let ::= (let (binding*) expression*)
binding ::= (variable expression)

let* ::= (let* (binding*) expression*)

sequence ::=  (progn expression*)

while ::= (while test expression*)

XML Syntax

The grammar in this section is generated from the class definitions by a program that outputs plain text, which is why it is not as nicely formatted as the Lisp syntax. Identifiers that are written completely in upper case are the nonterminal symbols of the grammar. "::=" connects a nonterminal with its definition. "|" separates alternatives. "nonterminal..." indicates that zero or more instances of the nonterminal may appear.

EXPRESSION ::= AND | ASSIGNMENT | CALL | IF
            |  LAMBDA | LET | LITERAL | OR | SEQUENCE
            |  VAR-REF | WHILE

AND ::=
   <and>
      <of><list>EXPRESSION...</list></of>
   </and>

ASSIGNMENT ::=
   <assignment
         to="NAME">
      <value>EXPRESSION</value>
   </assignment>

BINDING ::=
   <binding
         name="NAME">
      <value>EXPRESSION</value>
   </binding>

CALL ::=
   <call>
      <function>EXPRESSION</function>
      <arguments><list>EXPRESSION...</list></arguments>
   </call>

I-SCRIPT-XML-SOURCE ::=
   <i-script-XML-source>
      <expression>EXPRESSION</expression>
   </i-script-XML-source>

IF ::=
   <if>
      <test>EXPRESSION</test>
      <if-true>EXPRESSION</if-true>
      <if-false>EXPRESSION</if-false>
   </if>

LAMBDA ::=
   <lambda>
      <parameters><list>NAME...</list></parameters>
      <in>EXPRESSION</in>
   </lambda>

LET ::=
   <let>
      <bindings><list>BINDING...</list></bindings>
      <in>EXPRESSION</in>
   </let>

LITERAL ::=
   <literal>
      <value>OBJECT</value>
   </literal>

OR ::=
   <or>
      <of><list>EXPRESSION...</list></of>
   </or>

SEQUENCE ::=
   <sequence>
      <of><list>EXPRESSION...</list></of>
   </sequence>

VAR-REF ::=
   <var-ref
         name="NAME">
   </var-ref>

WHILE ::=
   <while>
      <test>EXPRESSION</test>
      <repeat>EXPRESSION</repeat>
   </while>

Jeff Dalton <J.Dalton@ed.ac.uk>