Anonymous avatar Anonymous committed 1f83fda

Initial import of Sally 2003.1104 sources.

Comments (0)

Files changed (17)

Empty file added.

+Change Log for Sally
+--------------------
+
+2000.0226
+
+  Original release.
+  
+2003.1104
+
+  Added GNU Makefile.
+  Added bin/ and lib/ subdirectories.
+  Split sally.c into sally.c and runtime.c.
+  Added libsally library.
+<html><head>
+    <meta http-equiv="Content-Type" content="text/html;CHARSET=iso-8859-1">
+    <meta name="Description" content="Cat's Eye Technologies: The Sally Programming Language">
+    <title>Cat's Eye Technologies: The Sally Programming Language</title>
+</head>
+<body  bgcolor="#ffffff" text="#000000" link="#1c3f7f"
+      vlink="#204020" background="/img/sinewhite.gif" >
+<h1>Sally</h1>
+<p>v2003.1104 <img src="/images/icons/copyright.gif"
+   align=absmiddle width=12 height=12 alt="(c)" border=0>2000-2004
+   <a href="http://catseye.webhop.net/">Cat's Eye Technologies</a>.
+
+<h2>What is Sally?</h2>
+
+<p>Sally is basically FORTH, except:
+
+<ul>
+<li> All functions are declared with fixed range and domain types;
+<li> Strong type checking is applied to arguments and results;
+<li> User-defined types can be introduced into the checking scheme;
+<li> Forward, instead of reverse, Polish notation is used.
+</ul>
+
+<p>Sally is also an exercise in the reduction of excise (redundant,
+extraneous, or sugary syntax).
+
+<p>For example, there is, unlike FORTH, no special symbol to indicate
+the end of a function definition.  (A new definition starts whenever
+the previous one ends.)
+
+<p>The ANSI C source code for the compiler is very small, less than
+16K in total.  The compiler translates Sally programs to ANSI C.
+
+<p>Just to be silly I've scattered exercises for the reader around the
+documentation.  I don't actually expect anyone to try any of them,
+but they kind of indicate what I'd like to see in a "Sally++" if
+there ever was such a beast.
+
+<h3>Syntax</h3>
+
+<p>A Sally program consists of a series of function declarations.
+Each declaration consists of the name and type of a new function
+followed by a series of function applications and primitives.
+
+<p>The domain types are listed before the function name, the range
+types, after.  For example, a function called <tt>foo</tt> which maps an
+integer and a character to an integer, would be notated as
+
+<pre>  int char foo int ...
+</pre>
+
+<p>The <tt>...</tt> represents the function applications which comprise the
+body of the function.
+
+<p>The syntax of each application is dictated by the types given in
+the function's definition.  For example, a correct syntax for
+applying the <tt>foo</tt> function above might be
+
+<pre>  foo 42 'X
+</pre>
+
+<p>(Note the lack of a need for parentheses.)  This application of
+foo would be appropriate anywhere a previous application requires
+an integer argument, or where a definition requires an integer
+result.
+
+<p>Functions can accept multiple arguments and return multiple results.
+A function which returns multiple results can pass those results as
+a 'chunk' to the previous function application.  For example, the
+following would return the double of the given argument <tt>$1</tt>:
+
+<pre>  add dup $1
+</pre>
+
+<p>And this would probably appear in a function definition like so:
+
+<pre>  int double int add dup $1
+</pre>
+
+<p>The type <tt>void</tt> indicates lack of any arguments or results.  When
+it indicates the lack of arguments, it must be specified explicitly
+(to indicate to the parser that the previous definition has ended.)
+When used to indicate the lack of results, it can be
+inferred by the fact that there are no types following the function
+name.
+
+<p>EXERCISE:  See if you can find a way to change the parser so that
+<tt>void</tt> is always implicit, even when it's used to indicate the
+lack of arguments to a function.  Be prepared to deal with a token
+which is an undeclared symbol in a mature way.
+
+<h3>Functions which Accept and Return Functions</h3>
+
+<p>A function can be passed to another function.  In order for a
+function to be defined which accepts a function passed to it, a
+prototype of the type of function to be passed must be defined.
+This prototype is then preceded in the type declaration by the
+<tt>like</tt> operator.
+
+<p>For example, say we want a function which accepts an integer
+and a function which maps an integer to another integer, and
+returns an integer.  To do this, first we establish the prototype
+function which is included in the arguments to the other function:
+
+<pre>  int map int proto
+</pre>
+
+<p>(This kind of definition, a "proto", also functions like a "forward"
+declaration in Pascal or an "extern" declaration in C.)
+
+<p>We then use the <tt>like</tt> operator in specifying the definition of the
+other function:
+
+<pre>  int like map other int ...
+</pre>
+
+<p>The function <tt>other</tt> now takes an integer and a function 'like map'
+(that is, a function which has the same domain and range types as
+the function called <tt>map</tt>, even if the body of <tt>map</tt> is not actually
+defined) and returns an integer.
+
+<p>Even so, how does an application pass a function to another function?
+You can't just name the function, because that indicates that you want
+to apply it and use the return value.  You must instead "reference" or
+"escape" the function by preceding it with <tt>the</tt>.  So to apply the
+<tt>other</tt> function above to a function such as <tt>negate</tt>, one would write
+
+<pre>  other 5 the negate
+</pre>
+
+<p>Assuming <tt>negate</tt> is declared with the same range and domain types as
+<tt>map</tt>, this should pass the function <tt>negate</tt> without trying to apply
+it (presumably leaving that up to the <tt>other</tt> function).
+
+<p>Speaking of which, there is one last issue to cover.  Once a function
+like <tt>other</tt> has a reference to a function like <tt>map</tt> passed to it,
+how does <tt>other</tt> use the passed function?
+
+<p>The answer is the <tt>do</tt> keyword.  <tt>do</tt> is followed by the number of
+an argument.  It is not unlike <tt>$1</tt>, but it does not simply evaluate to
+the argument, it actually calls it.  When this is the case, the
+argument better be a function (all that strong typing stuff applies.)
+
+<p>EXERCISE:  See if you can extend the <tt>the</tt> operator to provide
+lambda functions.  Use the following as a syntax guideline for how
+one would specify a lambda function:
+
+<pre>  other 5 the int -&gt; int + $1 7
+</pre>
+
+<p>Remember, there's no special "End Function Definition" symbol!
+
+<p>EXERCISE:  Extend <tt>do</tt> to handle <tt>the</tt> functions directly.  Example:
+
+<pre>  do the monkey
+</pre>
+
+<p>EXERCISE:  Finally, extend <tt>like</tt> to likewise handle <tt>the</tt> functions
+directly.  Example:
+
+<pre>  int like the int -&gt; int proto other int ...
+</pre>
+
+<h3>Type Checking and Casting</h3>
+
+<p>A named type can defined in Sally by defining it like you would define
+a function, but with no range type, and with no definition, instead the
+token <tt>type</tt>, as in:
+
+<pre>  int semaphore type
+</pre>
+
+<p>In Sally, two types are equivalent if:
+<ul>
+<li> Both are named and their names are the same; or
+<li> Neither is named and they are structurally equivalent.
+</ul>
+
+<p>(By named, I of course mean, named by the user, not intrinsic to the
+language.  Even though <tt>int</tt> is technically a name, it's unnamed for
+our purposes here.)
+
+<p>Values can be cast from one type to another.  This is invaluable for
+any structured data access in Sally.
+
+<p>No conversions are done during type casting.  Types can only be
+cast to other types of the same size (number of elements - you can
+cast <tt>char</tt> to <tt>int</tt> but not to <tt>int int</tt> or <tt>void</tt>.)
+
+<p>Typecasts are performed with the <tt>as</tt> operator, as in
+
+<pre>  as char 7
+</pre>
+
+<p>to represent a bell.
+
+<p>EXERCISE:  Implement type variables, so that one could define
+functions like
+
+<pre>  `1 `2 swap `2 `1 $2 $1
+</pre>
+
+<p>Which would be applicable no matter what types were passed to and
+received from <tt>swap</tt>, as long as the types were consistent (all
+<tt>`1</tt>'s are the same type and all <tt>`2</tt>'s are the same type for any
+given application of <tt>swap</tt>.)
+
+<p>There are several ways one may want to attempt this.  One is by
+using the process of <i>unification</i> to make sure all type variables
+are used consistently.  Adding this to Sally may be excessively
+tricky because of the way it does type checking.  With a stack of
+types, there may be a more efficient algorithm for replacing type
+variables with instances, and subsequently checking them for
+consistency.
+
+<h3>Libraries, Side Effects, and <tt>main</tt></h3>
+
+<p>Libraries can be included before the first function definition in a
+program.  There is no special "include" token, the library is simply
+named, and if a file named that (plus the extension <tt>.sal</tt>) is located,
+it is (virtually) inserted into that point in the program.
+
+<p>For example, many of the sample programs begin with the token
+<tt>stdlib</tt>.  This loads the file stdlib.sal into that point in the
+program, introducing a handful of function prototypes.
+
+<p>Libraries are also how Sally deals with side effects.  The philosophy
+is that if the programmer wants to disturb the purity of the functional
+paradigm by introducing side effects, they may do so, but they will be
+made clearly aware of the fact.
+
+<p>Having said that, Sally can only perform side effect communications
+by including the library called <tt>sidefxio</tt> - thus reminding the
+programmer that there are side effect communications at work in the
+following program.
+
+<p>Without including this library Sally is limited to batch
+communications.
+
+<p>In both schemes, the function called <tt>main</tt> is the function which is
+applied when the entire program is run.  <tt>main</tt> may have any number
+of arguments and any number of return values, although they may only
+be of <tt>int</tt> type.  For each argument, a value is required as a
+command-line argument when the program is run; for each result, the
+resultant value is displayed at the end of the program.
+
+<p>This little communications scheme is minimal, and limited, but it
+does not introduce any side effects in any way, and is capable of
+communicating any Turing-solvable problem, so it has some things
+going for it.  To get around the limitations, however, you have to
+resort to side effect I/O, where you can use the 'print' and
+'input' functions to report and obtain information from the user
+while the program is running.
+
+<p>EXERCISE:  Loosen the constraints on the type of the <tt>main</tt>
+function - allow arguments and return values of type <tt>char</tt>.
+
+<h3>EBNF Grammar</h3>
+
+<pre>  Program     ::= {Definition}.
+  Definition  ::= {Library} {Type} Name {Type}
+                  ("type" | "proto" | {Application}).
+  Type        ::= "int" | "char" | "like" Name | Name.
+  Application ::= Primitive
+                | "$" Number
+	        | (Name | "do" Number) {Instr}
+                | "as" {Type} Instr
+	        | "if" Instr Instr Instr
+                | "the" Name.
+  Primitive   ::= &lt;&lt;an integer notated in decimal like 123&gt;&gt;
+                | &lt;&lt;a character preceded by a single quote like 'A&gt;&gt;.
+</pre>
+
+<center><p><font size=-1>  
+Last Updated Sep 20&nbsp;<img src="/images/icons/copyright.gif"
+   align=absmiddle width=12 height=12 alt="(c)" border=0>2004 <a
+   href="http://catseye.webhop.net/">Cat's Eye Technologies</a>.
+</font></center>
+</body></html>
+                                 Sally
+                       A Strongly-Typed Language
+                       -------------------------
+   v2000.02.26 (c)2000 Cat's-Eye Technologies.  All rights reserved.
+
+What is Sally?
+--------------
+
+Sally is basically FORTH, except:
+
+- All functions are declared with fixed range and domain types
+- Strong type checking is applied to arguments and results
+- User-defined types can be introduced into the checking scheme
+- Forward, instead of reverse, Polish notation is used
+
+Sally is also an exercise in the reduction of excise (redundant,
+extraneous, or sugary syntax).
+
+For example, there is, unlike FORTH, no special symbol to indicate
+the end of a function definition.  (A new definition starts whenever
+the previous one ends.)
+
+The ANSI C source code for the compiler is very small, less than
+16K in total.  The compiler translates Sally programs to ANSI C.
+
+Just to be silly I've scattered exercises for the reader around the
+documentation.  I don't actually expect anyone to try any of them,
+but they kind of indicate what I'd like to see in a "Sally++" if
+there ever was such a beast.
+
+Syntax
+------
+
+A Sally program consists of a series of function declarations.
+Each declaration consists of the name and type of a new function
+followed by a series of function applications and primitives.
+
+The domain types are listed before the function name, the range
+types, after.  For example, a function called foo which maps an
+integer and a character to an integer, would be notated as
+
+  int char foo int ...
+
+The '...' represents the function applications which compose the
+body of the function.
+
+The syntax of each application is dictated by the types given in
+the function's definition.  For example, a correct syntax for
+applying the 'foo' function above might be
+
+  foo 42 'X
+
+(Note the lack of a need for parentheses.)  This application of
+foo would be appropriate anywhere a previous application requires
+an integer argument, or where a definition requires an integer
+result.
+
+Functions can accept multiple arguments and return multiple results.
+A function which returns multiple results can pass those results as
+a 'chunk' to the previous function application.  For example, the
+following would return the double of the given argument '$1':
+
+  add dup $1
+
+And this would probably appear in a function definition like so:
+
+  int double int add dup $1
+
+The type 'void' indicates lack of any arguments or results.  When
+it indicates the lack of arguments, it must be specified explicitly
+(to indicate to the parser that the previous definition has ended.)
+When used to indicate the lack of results, it can be implicitly
+inferred by the fact that there are no types following the function
+name.
+
+EXERCISE:  See if you can find a way to change the parser so that
+'void' is always implicit, even when it's used to indicate the
+lack of arguments to a function.  Be prepared to deal with a token
+which is an undeclared symbol in a mature way.
+
+Functions which Accept and Return Functions
+-------------------------------------------
+
+A function can be passed to another function.  In order for a
+function to be defined which accepts a function passed to it, a
+prototype of the type of function to be passed must be defined.
+This prototype is then preceded in the type declaration by the
+'like' operator.
+
+For example, say we want a function which accepts an integer
+and a function which maps an integer to another integer, and
+returns an integer.  To do this, first we establish the prototype
+function which is included in the arguments to the other function:
+
+  int map int proto
+
+(This kind of definition, a "proto", also functions like a "forward"
+declaration in Pascal or an "extern" declaration in C.)
+
+We then use the 'like' operator in specifying the definition of the
+other function:
+
+  int like map other int ...
+
+The function 'other' now takes an integer and a function 'like map'
+(that is, a function which has the same domain and range types as
+the function called 'map', even if the body of 'map' is not actually
+defined) and returns an integer.
+
+Even so, how does an application pass a function to another function?
+You can't just name the function, because that indicates that you want
+to apply it and use the return value.  You must instead "reference" or
+"escape" the function by preceding it with "the".  So to apply the
+'other' function above to a function such as 'negate', one would write
+
+  other 5 the negate
+
+Assuming 'negate' is declared with the same range and domain types as
+'map', this should pass the function 'negate' without trying to apply
+it (presumably leaving that up to the 'other' function).
+
+Speaking of which, there is one last issue to cover.  Once a function
+like 'other' has a reference to a function like 'map' passed to it,
+how does 'other' use the passed function?
+
+The answer is the "do" keyword.  "do" is followed by the number of
+an argument.  It is not unlike $1, but it does not simply evaluate to
+the argument, it actually calls it.  When this is the case, the
+argument better be a function (all that strong typing stuff applies.)
+
+EXERCISE:  See if you can extend the "the" operator to provide
+lambda functions.  Use the following as a syntax guideline for how
+one would specify a lambda function:
+
+  other 5 the int -> int + $1 7
+
+Remember, there's no special "End Function Definition" symbol!
+
+EXERCISE:  Extend "do" to handle "the" functions directly.  Example:
+
+  do the monkey
+
+EXERCISE:  Finally, extend "like" to likewise handle "the" functions
+directly.  Example:
+
+  int like the int -> int proto other int ...
+
+Type Checking and Casting
+-------------------------
+
+A named type can defined in Sally by defining it like you would define
+a function, but with no range type, and with no definition, instead the
+token 'type', as in:
+
+  int semaphore type
+
+In Sally, two types are equivalent if:
+- Both are named and their names are the same; or
+- Neither is named and they are structurally equivalent.
+
+(By named, I of course mean, named by the user, not intrinsic to the
+language.  Even though 'int' is technically a name, it's unnamed for
+our purposes here.)
+
+Values can be cast from one type to another.  This is invaluable for
+any structured data access in Sally.
+
+No conversions are done during type casting.  Types can only be
+cast to other types of the same size (number of elements - you can
+cast 'char' to 'int' but not to 'int int' or 'void'.)
+
+Typecasts are performed with the "as" operator, as in
+
+  as char 7
+
+to represent a bell.
+
+EXERCISE:  Implement type variables, so that one could define
+functions like
+
+  `1 `2 swap `2 `1 $2 $1
+
+Which would be applicable no matter what types were passed to and
+received from 'swap', as long as the types were consistent (all
+`1's are the same type and all `2's are the same type for any
+given application of 'swap'.)
+
+There are several ways one may want to attempt this.  One is by
+using the process of 'unification' to make sure all type variables
+are used consistently.  Adding this to Sally may be excessively
+tricky because of the way it does type checking.  With a stack of
+types, there may be a more efficient algorithm for replacing type
+variables with instances, and subsequently checking them for
+consistency.
+
+Libraries, Side Effects, and main
+---------------------------------
+
+Libraries can be included before the first function definition in a
+program.  There is no special "include" token, the library is simply
+named, and if a file named that (plus the extension .sal) is located,
+it is (virtually) inserted into that point in the program.
+
+For example, many of the sample programs begin with the token
+'stdlib'.  This loads the file stdlib.sal into that point in the
+program, introducing a handful of function prototypes.
+
+Libraries are also how Sally deals with side effects.  The philosophy
+is that if the programmer wants to disturb the purity of the functional
+paradigm by introducing side effects, they may do so, but they will be
+made clearly aware of the fact.
+
+Having said that, Sally can only perform side effect communications
+by including the library called 'sidefxio' - thus reminding the
+programmer that there are side effect communications at work in the
+following program.
+
+Without including this library Sally is limited to batch
+communications.
+
+In both schemes, the function called 'main' is the function which is
+applied when the entire program is run.  'main' may have any number
+of arguments and any number of return values, although they may only
+be of "int" type.  For each argument, a value is required as a
+command-line argument when the program is run; for each result, the
+resultant value is displayed at the end of the program.
+
+This little communications scheme is minimal, and limited, but it
+does not introduce any side effects in any way, and is capable of
+communicating any Turing-solvable problem, so it has some things
+going for it.  To get around the limitations, however, you have to
+resort to side effect I/O, where you can use the 'print' and
+'input' functions to report and obtain information from the user
+while the program is running.
+
+EXERCISE:  Loosen the constraints on the type of the 'main'
+function - allow arguments and return values of type 'char'.
+
+EBNF Grammar
+------------
+
+  Program     ::= {Definition}.
+  Definition  ::= {Library} {Type} Name {Type}
+                  ("type" | "proto" | {Application}).
+  Type        ::= "int" | "char" | "like" Name | Name.
+  Application ::= Primitive
+                | "$" Number
+	        | (Name | "do" Number) {Instr}
+                | "as" {Type} Instr
+	        | "if" Instr Instr Instr
+                | "the" Name.
+  Primitive   ::= <<an integer notated in decimal like 123>>
+                | <<a character preceded by a single quote like 'A>>.
+stdlib
+int factorial int if $1 mul $1 factorial sub $1 1 1
+int main int factorial $1
+stdlib
+int main int char
+  sub dup $1 pop 4 'a'
+sidefxio
+void main
+     print 'H
+     print 'e
+     print 'l
+     print 'l
+     print 'o
+     print ',
+     print as char 32
+     print 'w
+     print 'o
+     print 'r
+     print 'l
+     print 'd
+     print '!
+
+char print proto
+void input char proto
+int int add int proto
+int int sub int proto
+int int mul int proto
+int int div int proto
+    int dup int int proto
+    int pop proto
+
+stdlib
+int int binop int
+  proto
+int int like binop dobinop int
+  do 3 $1 $2
+int main int int
+  dobinop $1 5 the add dobinop $1 5 the sub
+stdlib
+int semaphore type
+semaphore signal semaphore as semaphore sub as int $1 1
+semaphore wait semaphore as semaphore add as int $1 1
+
+void dosemaphores int as int wait signal wait wait as semaphore 0
+
+int int coord type
+int int swap int int $2 $1
+int int mkcoord coord as coord $1 $2
+coord getxy int int as int int $1
+
+int int main int int int
+  getxy mkcoord $1 $2
+  dosemaphores

Empty file added.

+# GNU Makefile for sally
+# Created 2003.1104 Chris Pressey, Cat's Eye Technologies
+
+# CC=gcc
+CFLAGS=-ansi -pedantic -g -Wall -O
+
+OBJECTS= sally.o sally2c.o
+
+all: ../lib/libsally.a ../bin/sally2c
+
+sally.o: sally.c sally.h
+
+sally2c.o: sally2c.c sally.h
+
+runtime.o: runtime.c
+
+../lib/libsally.a: runtime.o
+	ar rc ../lib/libsally.a runtime.o
+	ranlib ../lib/libsally.a
+
+../bin/sally2c: $(OBJECTS)
+	$(CC) -o../bin/sally2c $(OBJECTS)
+	strip ../bin/sally2c
+
+clean:
+	rm *.o
+	rm ../bin/*
+	rm ../lib/*
+/*
+  runtime.c: Sally language runtime support v2003.1104
+  (c)2003 Cat's Eye Technologies.  All rights reserved.
+*/
+
+#include <stdio.h>
+
+/******************************    RUNTIME    ******************************/
+
+int stack[256];
+int sp=0;
+
+int pop(void)
+{
+  if (sp > 0) return stack[sp--]; else return 0;
+}
+
+void push(int i)
+{
+  if (sp < 255) stack[++sp] = i;
+}
+
+void apply_add(void)
+{
+  int arg2 = pop();
+  int arg1 = pop();
+  push(arg1 + arg2);
+}
+
+void apply_sub(void)
+{
+  int arg2 = pop();
+  int arg1 = pop();
+  push(arg1 - arg2);
+}
+
+void apply_mul(void)
+{
+  int arg2 = pop();
+  int arg1 = pop();
+  push(arg1 * arg2);
+}
+
+void apply_div(void)
+{
+  int arg2 = pop();
+  int arg1 = pop();
+  push(arg1 / arg2);
+}
+
+void apply_dup(void)
+{
+  int arg1 = pop();
+  push(arg1);
+  push(arg1);
+}
+
+void apply_pop(void)
+{
+  pop();
+}
+
+void apply_print(void)
+{
+  fprintf(stdout, "%c", (char)pop());
+}
+
+void apply_input(void)
+{
+  push(fgetc(stdin));
+}
+
+/* END of runtime.c */
+/*
+  sally.c: Sally language subroutines v2003.1104
+  (c)2003 Cat's Eye Technologies.  All rights reserved.
+*/
+
+#include <string.h>
+#include <ctype.h>
+
+#include "sally.h"
+
+/******************************  TYPE SYSTEM  ******************************/
+
+type * typestack[256];
+int tsp = 0;
+
+type * debit_type(void) /* pop type from type stack */
+{
+  if (tsp > 0) return typestack[tsp--];
+  error("Type underflow");
+  return NULL;
+}
+
+void credit_type(type * t) /* push type onto type stack */
+{
+  if (tsp < 255) typestack[++tsp] = t; else error("Type Overflow");
+}
+
+type * construct_type(int id, type * of, type * to)
+{
+  type * t = (type *)malloc(sizeof(type));
+  if (t != NULL)
+  {
+    t->id = id;
+    t->of = of;
+    t->to = to;
+    t->name = NULL;
+  }
+  return t;
+}
+
+type * construct_pair(type * a, type * b)
+{
+  if (a == NULL) return b;
+  if (b == NULL) return a;
+  return construct_type(TYPEID_pair, a, b);
+}
+
+type * construct_function(type * a, type * b)
+{
+  return construct_type(TYPEID_func, a, b);
+}
+
+type * unname_type(type * a)
+{
+  if (a == NULL) return NULL;
+  if (a->id >= 128)
+    return construct_type(a->id, unname_type(a->of), unname_type(a->to));
+  if (a->name == NULL) return a;
+  return a->of;
+}
+
+int count_type(type * x)  /* returns number of primitives in tuple */
+{
+  if (x == NULL) return 0;
+  if (x->id != TYPEID_pair) return 1;
+  return count_type(x->of) + count_type(x->to);
+}
+
+type * nth_type(type * x, int n) /* returns one primitive from a tuple */
+{
+  int l = count_type(x);
+  while (n < l && x != NULL && x->id == TYPEID_pair)
+  {
+    l--;
+    x = x->of;
+  }
+  if (x->id == TYPEID_pair) x = x->to;
+  return x;
+}
+
+type * domain_type(type * x) /* returns type of arguments to function */
+{
+  if (x == NULL) return NULL;
+  if (x->id == TYPEID_func) return x->of;
+  return x;
+}
+
+type * range_type(type * x) /* returns type of result of function */
+{
+  if (x == NULL) return NULL;
+  if (x->id == TYPEID_func) return x->to;
+  return x;
+}
+
+int equivalent_types(type * a, type * b)
+{
+  if (a == b) return 1;
+  if (a == NULL || b == NULL) return 0;
+  if (a->name != NULL && b->name != NULL) return (a->name == b->name);
+  if (a->id == b->id)
+  {
+    if (a->id >= 128) return equivalent_types(a->of, b->of) &&
+			     equivalent_types(a->to, b->to);
+		 else return 1;
+  }
+  return 0;
+}
+
+void print_type(FILE * f, type * t)
+{
+  if (t==NULL)
+  {
+    fprintf(f, "void");
+    return;
+  } else
+  if (t->name != NULL)
+  {
+    fprintf(f, "%s", t->name->id);
+  } else
+  switch(t->id)
+  {
+    case TYPEID_type: fprintf(f, "type"); break;
+    case TYPEID_int:  fprintf(f, "int"); break;
+    case TYPEID_char: fprintf(f, "char"); break;
+    case TYPEID_pair: print_type(f, t->of);
+		      fprintf(f, ", ");
+		      print_type(f, t->to); break;
+    case TYPEID_func: fprintf(f, "{");
+		      print_type(f, t->of);
+		      fprintf(f, " -> ");
+		      print_type(f, t->to);
+		      fprintf(f, "}"); break;
+    case TYPEID_many: fprintf(f, "many ");
+		      print_type(f, t->of); break;
+    default: fprintf(f, "type error (%d)", t->id);
+  }
+}
+
+/****************************** SYMBOL TABLE ******************************/
+
+symbol * head = NULL;
+
+/* assumed: preceding call to sym_lookup failed. */
+symbol * sym_defn(char * s, type * t)
+{
+  symbol * h = head;
+  symbol * n = (symbol *)malloc(sizeof(symbol));
+  if (n == NULL)
+  {
+    fprintf(stderr, "Could not allocate symbol table record\n");
+  } else
+  {
+    n->id = (char *)malloc(strlen(s)+1);
+    if (n->id == NULL)
+    {
+      fprintf(stderr, "Could not allocate lexeme\n");
+    } else
+    {
+      strcpy(n->id, s);
+      n->t = t;
+      n->next = head;
+      head = n;
+      return n;
+    }
+  }
+  return NULL;
+}
+
+symbol * sym_lookup(char * s)
+{
+  symbol * h = head;
+  while(h != NULL)
+  {
+    if(!strcmp(s, h->id)) return h;
+    h = h->next;
+  }
+  return NULL;
+}
+
+/******************************    SCANNER    ******************************/
+
+FILE * infile;
+FILE * outfile;
+char   token[256];
+int    lino = 1;
+int    column = 0;
+
+int isatype(void)
+{
+  symbol * s = sym_lookup(token);
+  if (s != NULL && s->t->id == TYPEID_type) return 1;
+  if (tokeq("void") || tokeq("int") || tokeq("char") || tokeq("like")) return 1;
+  return 0;
+}
+
+void error(char * s)
+{
+  fprintf(stderr, "Error (line %d, column %d, token '%s'): %s.\n",
+	  lino, column, token, s);
+}
+
+void scan(void)
+{
+  char x;
+  int i = 0;
+
+  chkeof;
+  x = (char)getc(infile); column++;
+  chkeof;
+  while (x <= ' ')
+  {
+    if (x == '\n') { lino++; column = 0; }
+    x = (char)getc(infile); column++;
+    chkeof;
+  }
+
+  if (x == '"')
+  {
+    token[i++] = x;
+    x = (char)getc(infile); column++;
+    chkeof;
+    while (x != '"')
+    {
+      token[i++] = x;
+      x = (char)getc(infile); column++;
+      chkeof;
+    }
+    token[i] = 0;
+    return;
+  } else
+  if (!isspace(x) && !feof(infile))
+  {
+    while (!isspace(x) && !feof(infile))
+    {
+      token[i++] = x;
+      x = (char)getc(infile); column++;
+      chkeof;
+    }
+    ungetc(x, infile); column--;
+    token[i] = 0;
+    return;
+  } else
+  {
+    token[0] = 0;
+    return;
+  }
+}
+
+/******************************    PARSER    ******************************/
+
+type * application(type * func, type * avail)
+{
+  type * args = NULL;
+  type * q = NULL;
+  int i;
+
+  while(count_type(args) < count_type(domain_type(func))
+	&& token[0] != 0)
+    args = construct_pair(args, instruction(avail));
+
+  for(i=count_type(domain_type(func));i>=1;i--)
+    if(!equivalent_types(debit_type(), nth_type(domain_type(func),i)))
+      error("Type mismatch");
+
+  for(i=1;i<=count_type(range_type(func));i++)
+    credit_type(nth_type(range_type(func),i));
+
+  return range_type(func);
+}
+
+type * instruction(type * avail)
+{
+  type * mytype = NULL;  /* the type of this instruction */
+  symbol * s = sym_lookup(token);
+  if (tokeq("do"))
+  {
+    int argnum;
+    scan();
+    argnum = atoi(token);
+    if (argnum > count_type(avail))
+      error("Maximum argument count exceeded");
+    scan();
+    mytype = application(nth_type(avail, argnum), avail);
+    fprintf(outfile, "  (*arg%d)();\n", argnum);
+  } else
+  if (tokeq("the"))
+  {
+    scan();
+    s = sym_lookup(token);
+    scan();
+    mytype = s->t;
+    fprintf(outfile, "  push((int)&apply_%s);\n", s->id);
+    credit_type(mytype);
+  } else
+  if (tokeq("as"))
+  {
+    type * m = NULL;
+    int i = 0;
+    scan();
+    while(isatype())
+      mytype = construct_pair(mytype, parse_type());
+    while(i < count_type(unname_type(mytype)))
+    {
+      i += count_type(unname_type(instruction(avail)));
+      debit_type();
+    }
+    for(i=1;i<=count_type(mytype);i++)
+      credit_type(nth_type(mytype,i));
+  } else
+  if (tokeq("if"))
+  {
+    type * a = NULL;
+    type * b = NULL;
+    type * c = NULL; type * d = NULL;
+    scan();
+
+    a = instruction(avail);
+    fprintf(outfile, "  if(pop() != 0) {\n");
+    d = debit_type();
+
+    b = instruction(avail);
+    fprintf(outfile, "  } else {\n");
+    d = debit_type();
+
+    c = instruction(avail);
+    fprintf(outfile, "  }\n");
+    d = debit_type();
+
+    if (!equivalent_types(b, c)) error("Need equivalent types in 'if'");
+    mytype = b;
+    credit_type(mytype);
+  } else
+  if (isdigit(token[0]))
+  {
+    int litnum = atoi(token);
+    fprintf(outfile, "  push(%d);\n", litnum);
+    scan();
+    mytype = construct_type(TYPEID_int, NULL, NULL);
+    credit_type(mytype);
+  } else
+  if (token[0] == '\'')
+  {
+    int litnum = (int)token[1];
+    if (litnum==0) litnum = 32;
+    fprintf(outfile, "  push(%d);\n", litnum);
+    scan();
+    mytype = construct_type(TYPEID_char, NULL, NULL);
+    credit_type(mytype);
+  } else
+  if (token[0] == '$')
+  {
+    int argnum = atoi(token+1);
+    if (argnum <= count_type(avail))
+    {
+      int j;
+      type * x = nth_type(avail, argnum);
+      if (x->name != NULL)
+      {
+	for(j = 1; j <= count_type(unname_type(x)); j++)
+	  fprintf(outfile, "  push(arg%d_%d);\n", argnum, j);
+      } else fprintf(outfile, "  push(arg%d);\n", argnum);
+    } else error("Maximum argument count exceeded");
+    scan();
+    mytype = nth_type(avail, argnum);
+    credit_type(mytype);
+  } else
+  if (s != NULL)
+  {
+    char name[80];
+    strcpy(name, token);
+    scan();
+    mytype = application(s->t, avail);
+    fprintf(outfile, "  apply_%s();\n", name);
+  } else
+  {
+    error("Undefined symbol");
+    scan();
+  }
+  return mytype;
+}
+
+type * parse_type(void)
+{
+  type * t = NULL;
+  symbol * s = sym_lookup(token);
+
+  if (s != NULL)
+  {
+    if (s->t->id == TYPEID_type)
+    {
+      t = s->t;
+      scan();
+    }
+  } else
+  if (tokeq("void")) scan(); else
+  if (tokeq("int"))
+  {
+    t = construct_type(TYPEID_int, NULL, NULL);
+    scan();
+  } else
+  if (tokeq("char"))
+  {
+    t = construct_type(TYPEID_char, NULL, NULL);
+    scan();
+  } else
+  if (tokeq("like"))
+  {
+    scan();
+    s = sym_lookup(token);
+    if (s == NULL) error("Undefined function named in 'like'"); else
+    if (s->t->id == TYPEID_type) error("'like' needs function name, not type name");
+    t = s->t;
+    scan();
+  } else
+  {
+    error("Invalid type");
+    scan();
+  }
+  return t;
+}
+
+void definition(void)
+{
+  type * t = NULL;
+  type * u = NULL;
+  symbol * s = NULL;
+
+  while (!isatype() && token[0] != 0)
+  {
+    FILE * f;
+    FILE * g = infile;
+    int l = lino;
+    char fn[256];
+    sprintf(fn, "%s.sal", token);
+    f = fopen(fn, "r");
+    if (f != NULL)
+    {
+      infile = f;
+      scan();
+      while(token[0] != 0) definition();
+      infile = g;
+      fclose(f);
+    }
+    lino = l;
+    scan();
+  }
+
+  while(isatype()) t = construct_pair(t, parse_type());
+
+  if(sym_lookup(token) == NULL)
+  {
+    type * y = NULL;
+    char name[80];
+    strcpy(name, token);
+    scan();
+    if(tokeq("type"))
+    {
+      y = construct_type(TYPEID_type, t, NULL);
+      s = sym_defn(name, y);
+      y->name = s;
+      scan();
+    } else
+    {
+      while(isatype())
+        u = construct_pair(u, parse_type());
+      y = construct_function(t, u);
+      s = sym_defn(name, y);
+      fprintf(outfile, "/* ");
+      print_type(outfile, y);
+      fprintf(outfile, ": */ ");
+      if(tokeq("proto"))
+      {
+        fprintf(outfile, "void apply_%s(void);\n", name);
+        scan();
+      } else
+      if(s != NULL)
+      {
+	int i = 0, j = 0;
+	int main = 0;
+	int inputs = count_type(t);
+	type * v = NULL;
+
+	if(!strcmp(name, "main"))
+	{
+	  main = 1;
+	  fprintf(outfile, "int main(int argc, char ** argv)\n{\n");
+	  for(i=1; i <= inputs; i++)
+	    fprintf(outfile, "  int arg%d = atoi(argv[%d]);\n", i, i);
+  	fprintf(outfile, "  if(argc <= %d) { fprintf(stderr, \"%d values needed\"); exit(1); }\n", inputs, inputs);
+        } else
+	{
+	  fprintf(outfile, "void apply_%s(void)\n{\n", name);
+	  for(i = inputs; i >= 1; i--)
+	  {
+	    type * x = nth_type(t, i);
+	    if(x->name != NULL)
+	    {
+	      for(j = count_type(unname_type(x)); j >= 1; j--)
+		fprintf(outfile, "  int arg%d_%d = pop();\n", i, j);
+	      fprintf(outfile, "    /* ");
+	    } else
+	    switch(x->id)
+	    {
+	      case TYPEID_int:  fprintf(outfile, "  int arg%d = pop(); /* ", i); break;
+	      case TYPEID_char: fprintf(outfile, "  char arg%d = (char)pop(); /* ", i); break;
+	      case TYPEID_func: fprintf(outfile, "  void (*arg%d)(void) = (void (*)())pop(); /* ", i); break;
+	      default: fprintf(outfile, "  int arg%d = pop(); /* ", i);
+	    }
+	    print_type(outfile, x);
+	    fprintf(outfile, " */\n");
+          }
+        }
+
+        while(!isatype() && token[0] != 0)
+	  v = construct_pair(v, instruction(t));
+
+        for(i=count_type(range_type(s->t)); i >= 1; i--)
+	  if (!equivalent_types(debit_type(), nth_type(range_type(s->t), i)))
+	    error("Type mismatch");
+        if(tsp != 0) error("Type mismatch");
+
+        if(main)
+        {
+	  fprintf(outfile, "  {\n");
+	  for(i=count_type(range_type(s->t)); i >= 1; i--)
+	    fprintf(outfile, "    int result%d = pop();\n", i);
+	  for(i=1; i <= count_type(range_type(s->t)); i++)
+	    fprintf(outfile, "    printf(\"Result #%d: %cd\\n\", result%d);\n", i, '%', i);
+	  fprintf(outfile, "  }\n  argv = argv;\n  return 0;\n");
+        }
+
+        fprintf(outfile, "}\n\n");
+      } else error("Could not allocate symbol");
+    }
+  } else error("Symbol already declared");
+}
+
+/* End of sally.c */
+/*
+  sally.h: Sally language compiler header
+  (c)2000 Cat's-Eye Technologies.  All rights reserved.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+/******************************    RUNTIME    ******************************/
+
+extern int stack[];
+extern int sp;
+
+extern int pop(void);
+extern void push(int i);
+
+/******************************  TYPE SYSTEM  ******************************/
+
+#define TYPEID_type    0
+#define TYPEID_int     1
+#define TYPEID_char    2
+#define TYPEID_pair  128
+#define TYPEID_func  129
+#define TYPEID_many  130
+
+typedef struct Type
+{
+  int id;
+  struct Type * of;     /* for mappings (id >= 128) */
+  struct Type * to;     /* for mappings (id >= 128) */
+  struct Symbol * name; /* for named types & name equivalence */
+} type;
+
+extern type * typestack[];
+extern int tsp;
+
+extern type * construct_type(int id, type * of, type * to);
+extern type * construct_pair(type * a, type * b);
+extern type * construct_function(type * a, type * b);
+extern int count_type(type * x);  /* returns number of primitives in tuple */
+extern type * nth_type(type * x, int n); /* returns one primitives from a tuple */
+extern type * domain_type(type * x);
+extern type * range_type(type * x);
+extern int equivalent_types(type * a, type * b);
+extern void print_type(FILE * f, type * t);
+
+/****************************** SYMBOL TABLE ******************************/
+
+typedef struct Symbol
+{
+  char * id;
+  type * t;
+  struct Symbol * next;
+} symbol;
+
+extern symbol * head;
+
+extern symbol * sym_defn(char * s, type * t);
+extern symbol * sym_lookup(char * s);
+
+/******************************    SCANNER    ******************************/
+
+extern FILE * infile;
+extern FILE * outfile;
+extern char   token[];
+extern int    lino;
+
+#define tokeq(x)    (!strcmp(token,x))
+#define tokne(x)    (strcmp(token,x))
+#define chkeof      if (feof(infile)) { token[0] = 0; return; }
+
+extern int isatype(void);
+extern void error(char * s);
+extern void scan(void);
+
+/******************************    PARSER    ******************************/
+
+extern type * instruction(type * avail);
+extern type * parse_type(void);
+extern void definition(void);
+
+/* End of sally.h */
+/*
+  sally2c.c: Sally to C compiler (driver unit)
+  (c)2000 Cat's-Eye Technologies.  All rights reserved.
+*/
+
+#include <string.h>
+#include "sally.h"
+
+/****************************** MAIN PROGRAM ******************************/
+
+int main(int argc, char ** argv)
+{
+  infile = stdin;  outfile = stdout;
+  fprintf(outfile, "#include \"sally.h\"\n\n");
+  scan();
+  while(token[0] != 0) definition();
+  argc = argc; argv = argv;
+  return 0;
+}
+
+/* End of sally2c.c */
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.