Clef Programming Languages

Purpose

Clef is just a toy programming language that is designed to help demonstrate some of the principles of computation theory. It's called clef for no particular reason except that this name admits obvious variants for identifying variants of the language. Clef is not intended for general-purpose programming. Instead, it's specially designed as a tool for looking at different abstract notions of computation.

Clef has four interesting variants. Treble clef adds some features that make it easy to treat clef programs, themselves, as data. Thus, a treble clef program could take another treble clef program as input and produce a new program as output. The other three variants, alto, tenor and bass cleff can be seen as simpler programming languages with fewer features. These simpler languages help in the investigation of simpler models of computation.

Language Overview

Clef is an interpreted language. An interpreter for the language is located in the path /home/faculty/sturgill/public/bin/clef. You run a clef program by supplying it as an argument to the clef interpreter.

Standard Clef

One of the more interesting features of the basic language is that it is impossible to write a bad program. The language is defined by a context-free grammar and any program consistent with that grammar will run without producing errors. Of course, such a program may not actually do anything useful, but it is guaranteed to run.

Furthermore, it can be very hard to develop programs in a language that never produces errors. To help with this, clef supports a few command-line flags to specify the treatment of some things that are ordinarily considered errors. The -errors flag tells clef to halt whenever it encounters an error. The -warnings flag tells clef to just report errors and keep going. Finally, the -ignore tells clef to just ignore potential errors and keep going.

The following sections give a brief introduction to cleff. A few simple example programs are available at the end of this section.

Comments

Built-in Types

• Integer
  Like most programming languages, clef supports integers. Clef integers may be arbitrarily large.
  Examples:
  • Assign an integer value to the variable a :
    a = -57;
  • Print out a large integer value:
    writeln( 123456789012345678901234567890 );
• Symbol
  A symbol is a sequence of characters. Symbols can be used to represent variables, but they can also be used as values. Single quotes around a symbol indicate that the symbol should be taken as a symbol rather than a variable name.
  Examples:
  • Assign the symbol 'factor' to the variable a :
    a = 'factor';
  • Assign the value of the variable factor to the variable a :
    a = factor;
  • Print the symbol 'This is a test':
    writeln( 'This is a test' );
  
  The symbol nil is a special symbol. It is ordinarily supplied as the result of expressions that have no meaningful value. The symbols true and false are also special symbols with the obvious meaning. These three symbols are also special because they evaluate to themselves. Thus, I can say a := true and it means the same thing as a := 'true' .
• Array
  Arrays store a collection of values. Each value is associated with some index . The value may be an integer, a symbol or another array. The index must be either an integer or a symbol.

  Strings are special types of arrays. The length of a string is stored in element zero of the array. The individual characters in the string are stored in elements 1 .. length. Strings differ from symbols in that they are surrounded by double quotes and the individual characters in a string (which are, themselves, symbols) can be accessed by indexing into the array.
  Examples:

  • Store the symbol 'green' in element 5 of array a:
    a[5] = 'green;
  • Store the number 5 in element indexed by 'green' of array a:
    a['green'] = 5;
  • Store the string "This is a test" in array a:
    a = "this is a test";

Expressions

• Arithemetic
  Mathematical expressions operate on two integer-valued expressions. Clef provides the four basic arithmetic operators, + , - , * and / . Clef also supports modulation with the same notation as C, % .
  Example:
  • Evaluate an arithmetic expression and assign the result to a variable:
    c = a * ( b + 2 );
  
  
  
• Comparison
  Comparisons evaluate to true or false , depending on their arguments. Clef provides six comparison operators, == , != , < , > <= and >= . The inequality operators apply to integers while == and != work for integers or symbols.
  Examples:
  • Print 'greater' if the value of variable a is greater than 5:
    if a > 5 then writeln('greater');
  • Set color to 'green' if it is 'blue':
    if color == 'blue' then color = 'green';
  
  
• Boolean
  Clef provides the three standard boolean operators with the appropriate C-like syntax, and ( && ), or ( || ) and not ( ! ).
  Examples:
  • Print the word 'bounded' if the value of a is between -10 and 10:
    if( a > -10 && a < 10 ) writeln('greater');
  • Store a boolean value in variable z:
    z = a > -10;
  
  
• Function Call
  Expressions may include calls to functions.
  Examples:
  • Read a value, divide it by 2 and store the result in the variable half
    half = read() / 2;
  • Print the word 'prime' if the function is_prime() returns true:
    if is_prime(a) then writeln('prime');
  
  
• Assignment
  Variable assignment is considered an expression. It evaluates to the value of it's source expression. This permits C-like multiple assignments in a single statement:
  Assignment stores a value in a variable or in an array element. It's important to remember that everything in cleff is passed by value. Thus, the last example is legal.
  Examples:
  • Store the symbol 'blue' in the variable z:
    z = 'blue'
  • Copy the value of variable blue to the array in a at index 5:
    a[5] = blue
  • Take the (previous) value of a and put it in the array stored in a at index 5:
    a[5] = a

Statements

• Expressions
  Any expression can play the role of a statement. This makes it possible for assignments and function calls to behave just like statements. They just need a statement terminator at the end.
  
  
• if
  If statements contain a condition (an expression), a then statement and, optionally, an else statement. If the conditional expression evaluates to true, the then statement is executed. If the conditional expression evaluates to false, the else statement is executed if present. Note that, if the condition does not evaluate to true or false, neither the then nor the else statements will be performed.
  Examples:
  • Set variable a to 0 if it's less than 0:
    if( a < 0 ) a := 0
  • Print 'even' if a is even and 'odd' if it's odd.
    

    if( a % 2 == 0 )
        writeln('even');
      else
        writeln('odd'); 

  
  
• while
  While statements contain a condition (an expression) and a statement. The statement is executed as long as the condition evaluates to true.
  Example:
  • As long as variable a is odd, keep dividing it by 2:
    

    while( a % 2 != 0 )
          a := a div 2; 

  
  
• return
  The return statement causes the current function to terminate and return a value to the caller. The use of this statement is much like its C counterpart, except that return must always be given an expression to return. If no return value is desired, the symbol nil may be given.
  
• Compound Statement
  A compound statement is a sequence of statements surrounded by the symbols { and }. executing a compound statement is equivalent to executing the statements in this sequence
  Example:
  • Square a , print it, then subtract 5 from it.
    

     {
      a = a * a;
      writeln( a );
      a = a - 5;
    } 

Function Definitions

square(val)
{
   return val * val;
}

If a function needs local variables other than its formal parameters, these can be declared before the first opening curly brace. The syntax for local variables is more reminiscent of Pascal. They keyword var introduces a list of local variables. Names of local variables are separated with commas and the entire var declaration is terminated with a semicolon.

Built-in Functions

The function read() returns one value, which it reads from input. The type of value returned will depend on the input. Read is capable of processing integer, symbol or array input. Clef output and input formats are the same. Thus, an array printed as output of one clef program can be used as input to another.

Clef includes special functions geared toward language recognition. The functions accept() and reject() are used to accept or reject the input. If you must write a program that decides a particular language, your program should eventually call accept() on inputs that are in the language and reject() otherwise. Ordinarily, both accept() and reject() print an appropriate message and cause the program to terminate.

The enumerate procedure is just like writeln (i.e. it takes an arbitrary number of arguments). It is simply a specialized facility for enumerating a set. Why would you want this instead of just writeln? Well, in this class, well be concerned with a lot of formal details about computation. Using enumerate instead of writeln when listing the elements of a set is really just a policy. When you put enumerate in your code, you are saying that each call to enumerate prints out exactly one member of the set. The writeln function does not imply anything like this so we have a special enumerate function that carries this meaning. Although it functions jus like writeln, it is taken to mean something slightly different when we look at a program. In summary, if you are given the problem of enumerating a particular language, you should use one call of the enumerate procedure to write out each member of this language.

Clef also supports an include directive. This is much like the C include. It is used like:

#include "filename"

Clef Programs

Example Programs

//
// Accept the input string if it is a palindrome.
//

// read a value
{
  palin = read();

  length = palin[0];

  // walk through the first half and compare to last half

  point = 1;  point = 1;
  while( point <= length / 2 ) {
    if( palin[point] != palin[length - point + 1] )
      reject();

    point = point + 1;
  }

  accept();
}

//
// Determine the prime factorization of the input.
// It's not particularly efficient, but it makes a good example.
//

//
// Print the smallest factor in val and return the remainder.
//
fact(val)
var
   candidate;  // Candidate for a factor for val.
{
  candidate = 2;

  while( candidate < val  &&
         val % candidate != 0 )
     candidate = candidate + 1;

  writeln(candidate);
  return val / candidate;
}

{
   // read a value
   val = read();

   // Keep dividing out the smallest factor.

   while( val > 1 )
      val = fact(val);
}

//
// This program enumerates the set of all primes.
//

//
// Return true if val is prime.
//
isprime(val)
var
  fact,   // Potential factor for val
  pflag;  // True as long as we have not yet found an actual factor
{
   fact = 2;
   pflag = true;

   // Stop when we find a factor or once fact gets too big
   while( pflag &am;& fact * fact <= val ){
      if( val % fact == 0)
         pflag = false;
      fact = fact + 1;
   }

   return pflag;
}

{
  num = 2;

  // Check all integers 2 or greater for primeness.
  while( true ){
    if( isprime(num) )
      enumerate(num);

    num = num + 1;
  }
}

Treble Clef

Built-in Types

Built-in Functions

In treble clef, you can not only determine the types of different values by using identify, you an also take them appart. For example, a while statement is made up of a conditional part (an expression) and another statement. The function extract lets you pull out the individual components of the more complicated values (those after the first three). Extract takes two arguments. The second indicates the object from which you want to pull a component. The first indicates which component you want. The following table describes the different parts that make up each type of programatic element in cleff:

Type	Part Names
identifier	NamePart
array reference	LvaluePart	IndexPart
function call	NamePart	ArgPart
assignment	LvaluePart	SourcePart
if statement	ConditionPart	ThenPart	ElsePart
while statement	ConditionPart	DoPart
return statement	SourcePart
compound statement	ListPart
function definition	NamePart	ParamPart	VarPart	BodyPart
program definition	ListPart	BodyPart

Finally, there is a new function called create that makes values other integers, symbols and arrays. Create takes a variable number of arguments, depending on the first argument. The first argument specifies the type of object you want to create. It's the same as those given in the table above. Each type of value you might want to produce will require different arguments. In fact, the things you have to put into an object when you create it are exactly the tings you can take out of it via extraction. The order of items used in the above table corresponds to the order of arguments to create. Some of this will be made more clear in the examples given in the first homework.

A note about lists

A note if-then-else

A note about read

A great example

Alto Clef

Tenor Clef

Bass Clef