home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / oct93 / develop / umbscheme.lha / UMBScheme / src / compiler.c < prev    next >
C/C++ Source or Header  |  1992-08-04  |  14KB  |  588 lines
  1. /* compiler.c -- UMB Scheme, compiles Scheme expressions to abstract graphs.
  2.  
  3. UMB Scheme Interpreter                  $Revision: 2.5 $
  4. Copyright (C) 1988, 1991 William R Campbell
  5.  
  6. This program is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  
  20. UMB Scheme was written by Bill Campbell with help from Karl Berry,
  21. Barbara Dixey, Ira Gerstein, Mary Glaser, Kathy Hargreaves, Bill McCabe,
  22. Long Nguyen, Susan Quina, Jeyashree Sivasubram, Bela Sohoni and Thang Quoc Tran.
  23.  
  24. For additional information about UMB Scheme, contact the author:
  25.  
  26.     Bill Campbell
  27.     Department of Mathematics and Computer Science
  28.     University of Massachusetts at Boston
  29.     Harbor Campus
  30.     Boston, MA 02125
  31.  
  32.     Telephone: 617-287-6449        Internet: bill@cs.umb.edu
  33.  
  34. */
  35.  
  36.  
  37. #include    "portable.h"
  38. #include    "eval.h"
  39. #include    "object.h"
  40. #include    "architecture.h"
  41. #include    "compiler.h"
  42. #include     "steering.h"
  43. #include     "debug.h"
  44.  
  45. /*
  46.  
  47. In general, the compilation routines take their input expressions from atop
  48. the stack and leave the target graphs in the Value_Register.
  49.  
  50. */
  51.  
  52. #define Extend_Compiler_Environment( frame ) \
  53.     {    Get_Environment_Frame_Previous(frame) = Environment_Register;\
  54.         Environment_Register = frame; }
  55.  
  56. #define Restore_Compiler_Environment() \
  57.         Environment_Register = \
  58.             Get_Environment_Frame_Previous(Environment_Register);
  59.  
  60. Private void    Compile_Arguments();
  61. Private    void    Lookup_Address();
  62. Private Object    Scanned_Internal_Defns();
  63.  
  64.     
  65.  
  66. Public void Self_Compile()
  67. {
  68.     Value_Register = Top( 1 ) ;
  69.     Pop( 1 ) ;
  70. }
  71.  
  72.  
  73. Public void Compile_The_Empty_Object()
  74. {
  75.     Error( "Unquoted ()" );
  76. }
  77.  
  78.  
  79. Public void Compile_Form()
  80. {
  81.     /* The expression to be compiled is a list of the form
  82.  
  83.         (operator ...)
  84.     */
  85.  
  86.     Object    form = Top( 1 ) ;
  87.     Object    operator = First( form ) ;
  88.  
  89.     if ( Is_Symbol( operator ) )
  90.     {
  91.         if ( operator == QUOTE_Symbol )
  92.         {
  93.             /* form = (quote expr) */
  94.  
  95.             if ( Length( form ) != 2 )
  96.             {
  97.                 Display_Error("Bad syntax to quote in: ", form);
  98.             }
  99.  
  100.             Value_Register = Second( form ) ;
  101.         }
  102.         else if ( operator == DEFINE_Symbol )
  103.         {
  104.             Object name ;
  105.  
  106.             /* form = (define name expr) */
  107.  
  108.             if ( Length( form ) <  2 )
  109.             {
  110.             Display_Error("Bad syntax to define in: ", form);
  111.             }
  112.  
  113.             name = Second( form );
  114.  
  115.             if ( Is_Pair( name ) )
  116.             {
  117.             Object formals = Rest( name );
  118.  
  119.             /* Transform: (define (name . formals) . body)
  120.                 => (define name (lambda formals . body))
  121.             */
  122.  
  123.             name = First( name );
  124.  
  125.             Push( DEFINE_Symbol );
  126.             Push( name );
  127.             Push( LAMBDA_Symbol );
  128.             Push( formals );
  129.             Push( Rest( Rest( form )));
  130.  
  131.             Make_Pair();
  132.             Push( Value_Register );    /* (formals . body ) */
  133.             Make_Pair();
  134.             Push( Value_Register );    /* (lambda formals . body) */
  135.             Push( Nil );
  136.             Make_Pair();
  137.             Push( Value_Register );    /* ((lambda formals .body)) */
  138.             Make_Pair();
  139.             Push( Value_Register );    /* (name (lambda ...)) */
  140.             Make_Pair();
  141.             Push( Value_Register );    /* (define name (lambda...)) */
  142.  
  143.             Compile_Object( Top(1) ); /* Now, compile THAT! */
  144.             }
  145.             else
  146.             {
  147.             /* Basic form: (define name expr) */
  148.  
  149.             Object    expr ; 
  150.  
  151.             if ( Length( form ) != 3 )
  152.             {
  153.                 Display_Error("Bad syntax to define in: ", form);
  154.             }
  155.  
  156.             expr = Third( form );
  157.  
  158.             if ( !Is_Symbol( name ) )
  159.             {
  160.                 Display_Error("Bad syntax to define in: ", form);
  161.             }
  162.  
  163.             if (Get_Global_Binding(name) == The_Syntactic_Keyword)
  164.             {
  165.                 Error1( "`%s' cannot be used as a variable.",
  166.                     Get_Symbol_Name(name) );
  167.             }
  168.  
  169.             if ( Debugging && 
  170.                  Environment_Register ==     
  171.                 Get_State_Frame_Environment( State_Debugged ) )
  172.             {
  173.                 Lookup_Address( name , The_Global_Environment );
  174.             }
  175.             else
  176.             {
  177.                 Lookup_Address( name , Environment_Register );
  178.                 if ( Is_Local_Variable( Value_Register ) )
  179.                 {
  180.                 if (Get_Variable_Frame_Number(Value_Register)!=0)
  181.                     Display_Error( "Bad internal definition: ",
  182.                         form );
  183.                 }
  184.                 else if ((Environment_Register!=
  185.                         The_Global_Environment))
  186.                 {
  187.                     Display_Error( "Bad internal definition: ",form);
  188.                 }
  189.             }
  190.  
  191.             Push( Value_Register );
  192.  
  193.             Push( expr );
  194.             Compile_Object( Top( 1 ));
  195.             Push( Value_Register );
  196.  
  197.             Make_Definition();
  198.             }
  199.         }
  200.         else if ( operator == SET_Symbol )
  201.         {
  202.             /* form = (set! name expr) */
  203.  
  204.             if ( Length( form ) != 3 || !Is_Symbol(Second(form)) )
  205.             {
  206.                 Display_Error("Bad syntax to set! in: ", form);
  207.             }
  208.  
  209.             if (Get_Global_Binding(Second(form)) ==
  210.                 The_Syntactic_Keyword)
  211.             {
  212.                 Error1( "`%s' cannot be used as a variable.",
  213.                     Get_Symbol_Name(Second(form)) );
  214.             }
  215.  
  216.  
  217.             Lookup_Address( Second( form ) , Environment_Register );
  218.             Push( Value_Register );
  219.  
  220.             Push( Third( Top( 2 ) ) ); /* expr */
  221.             Compile_Object( Top( 1 ));
  222.             Push( Value_Register ); 
  223.  
  224.             Make_Assignment();
  225.         }
  226.         else if ( operator == IF_Symbol )
  227.         {
  228.             /* form = (if test consequent alternative)
  229.                  or   (if test consequent)
  230.             */
  231.  
  232.             if ( Length( form ) < 3 || Length( form ) > 4 )
  233.             {
  234.                 Display_Error("Bad syntax to if in: ", form);
  235.             }
  236.  
  237.             Push( Second( form )); /* form now = Top(2) */
  238.             Compile_Object( Top( 1 ));
  239.             Push( Value_Register );    /* test on stack */
  240.  
  241.             Push( Third( Top(2)) ); /* form now = Top(3) */
  242.             Compile_Object( Top( 1 ));
  243.             Push( Value_Register );    /* consequent on stack */
  244.  
  245.             if (Length( Top(3) ) == 4) 
  246.             {
  247.                 /* alternative supplied in form */
  248.  
  249.                 Push( Fourth( Top(3) )); 
  250.                 Compile_Object( Top( 1 ));
  251.                 Push( Value_Register );
  252.             }
  253.             else
  254.             {
  255.                 /* no alternative in form; use () instead */
  256.  
  257.                 Push( Nil );
  258.             }            /* alternative on stack */
  259.  
  260.             Make_Conditional();
  261.         }
  262.         else if ( operator == MACRO_Symbol )
  263.         {
  264.             /* form = (macro keyword transformer) */
  265.  
  266.             if ( Length( form ) != 3 || !Is_Symbol(Second(form)) )
  267.             {
  268.                 Display_Error("Bad syntax to macro in: ", form);
  269.             }
  270.  
  271.             Make_Global_Variable(Second(form));/* defined keyword */
  272.             Push( Value_Register );
  273.  
  274.             /* The Macro Object */
  275.  
  276.             form = Top( 2 );
  277.             Push( Second( form ) );    /* keyword on stack */
  278.             Push( Third( form ) );
  279.             Compile_Object( Top( 1 ));
  280.             Push( Value_Register );    /* transformer on stack */
  281.             Make_Macro();
  282.  
  283.             Push( Value_Register );        /* the macro */
  284.             Make_Definition();
  285.         }
  286.         else if ( operator == BEGIN_Symbol )
  287.         {
  288.             /* form = (begin . expr-sequence) */
  289.  
  290.             Push( Rest( form ));
  291.             Compile_Arguments();
  292.             Push( Value_Register );    /* expr-sequence on stack */
  293.             Make_Sequence(TRUE);
  294.         }
  295.         else if ( operator == DELAY_Symbol )
  296.         {
  297.             /* form = (delay expr) */
  298.  
  299.             if ( Length( form ) != 2 )
  300.             {
  301.                 Display_Error("Bad syntax to delay in: ", form);
  302.             }
  303.  
  304.             Push( Second( form ));
  305.             Compile_Object( Top( 1 ));
  306.             Push( Value_Register ); /* expr on stack */
  307.             Make_Delay();
  308.         }
  309.         else if ( operator == LAMBDA_Symbol )
  310.         {
  311.             /* form = (lambda formals . body ) */
  312.  
  313.             Object     formals = Second( form );
  314.             Object    formal_check;
  315.             Boolean    internal_definitions = FALSE;
  316.                         
  317.                         formal_check = formals;
  318.                         while (Is_Pair(formal_check))
  319.                         {
  320.                            if (! Is_Symbol(First(formal_check)))
  321.                            {
  322.                 Display_Error("Formals must be symbols", 
  323.                                         First(formal_check));
  324.                            }
  325.                else if ( Member( First(formal_check),
  326.                          Rest(formal_check) ))
  327.                {
  328.                 Display_Error( "Name duplicated in formals: ",
  329.                         First( formal_check ) );
  330.                }
  331.                formal_check = Rest( formal_check );
  332.  
  333.             }
  334.                         if (! Is_Symbol(formal_check) && formal_check != Nil)
  335.                         {
  336.                            Display_Error("Bad syntax for formal arguments",
  337.                                     formals);
  338.                         }
  339.                            
  340.             Push( formals );    /* formals */
  341.             Make_Symbol_Frame();
  342.             Extend_Compiler_Environment( Value_Register );
  343.             Push( Value_Register );
  344.  
  345.  
  346.             Push( Rest( Rest( Top(2) )));     /* body */
  347.             formals = Scanned_Internal_Defns( Top(1) );
  348.             if ( formals != Nil )
  349.             {
  350.                 internal_definitions = TRUE;
  351.                 Push( formals );
  352.                 Make_Symbol_Frame();
  353.                 Extend_Compiler_Environment( Value_Register );
  354.             }
  355.  
  356.             Compile_Arguments();     /* ie the body -- clause list */
  357.             Push( Value_Register );    
  358.  
  359.             if ( internal_definitions )
  360.             {
  361.                 /* The body contains internal definitions; we
  362.                    transform it to a new body as follows:
  363.  
  364.                    If body =
  365.  
  366.                     (   (define x1 e1)
  367.                         (define x2 e2)
  368.                         ...
  369.                         (define xn en) ...)
  370.  
  371.                    then we transform it to the new body:
  372.  
  373.                     ( ( (lambda (x1 x2 ... xn) body)
  374.                             ?1 ?2 ... ?n) . () )
  375.  
  376.                    Currently,
  377.  
  378.                     body is atop the stack, ie Top(1)
  379.                     formals = (xn ... x2 x1) 
  380.                 */
  381.  
  382.                 Integer numargs;
  383.                 Integer args;
  384.  
  385.                 formals = Environment_Register;
  386.                 numargs = Get_Environment_Frame_Size( formals );
  387.                 Restore_Compiler_Environment();
  388.  
  389.                 Push( formals );    /* (x1 ... xn) */
  390.                 Push( Top(2) );        /* orig body */
  391.                 Make_Sequence(FALSE);
  392.                 Push( Value_Register );
  393.                 Make_Lambda();
  394.                 Push( Value_Register );    /* (lambda (x1..xn)..)*/
  395.  
  396.                 args = numargs;
  397.                 while (args--) Push( The_Undefined_Symbol );
  398.                 Push( Nil );
  399.                 args = numargs;
  400.                 while (args--)
  401.                 {
  402.                     Make_Pair();
  403.                     Push( Value_Register );
  404.                 }            /* (?1 ... ?n) */
  405.  
  406.                 Make_Apply();
  407.                 Push( Value_Register );
  408.                 Push( Nil );
  409.                 Make_Pair();        /* the new body */
  410.                 Top(1) = Value_Register;/* replaces orig body */
  411.             }
  412.  
  413.             Restore_Compiler_Environment();
  414.             Make_Sequence(FALSE);    /* make the body a sequence */
  415.             Push( Value_Register );
  416.  
  417.             Make_Lambda();
  418.         }
  419.         else /* operator is not special */
  420.         {
  421.             /* (operator . arguments) */
  422.  
  423.             Value_Register = Get_Global_Binding( operator );
  424.             if ( Is_Macro( Value_Register ))
  425.             {
  426.                 /* NB: Macros are declared only in the global
  427.                        environment.
  428.                 */
  429.  
  430.                 /* Expand the macro call; compile result */
  431.  
  432.                 Boolean save_activation = Debugger_Activated;
  433.  
  434.                 Push( form ); /* Original code */
  435.  
  436.                 Push( Get_Macro_Transformer( Value_Register ) );
  437.  
  438.                 Push( form );
  439.                 Push( Nil );
  440.                 Make_Pair();
  441.                 Push( Value_Register );    /* (form) as arglist */
  442.  
  443.                 Make_Apply();  /* (transformer form) */
  444.  
  445.                 Push( Value_Register );
  446.                 Save(); /* !!!! */
  447.                 Debugger_Activated = FALSE;
  448.                 Eval( Top( 1 ), The_Global_Environment );
  449.                 Debugger_Activated = save_activation;
  450.                 Restore(); /* !!!! */
  451.                 Pop( 1 );
  452.                 Push( Value_Register );    /* Expansion on stack */
  453.  
  454.                 Compile_Object(Top(1)); /* Now, compile THAT! */
  455.                 Push( Value_Register );
  456.                 Make_Macro_Call();  /* from orig. & expansion */
  457.             }
  458.             else  /* An application */
  459.             {
  460.                 Push( operator );
  461.                 Compile_Object( Top( 1 ));
  462.                 Push( Value_Register );    /* operator on stack */
  463.  
  464.                 Push( Rest( Top( 2 ) ));
  465.                 Compile_Arguments();
  466.                 Push( Value_Register ); /* arguments on stack */
  467.  
  468.                 Make_Apply();
  469.             }
  470.         }
  471.     }
  472.     else /* operator is not a symbol -- treat as an application */
  473.     {
  474.         /* (operator . arguments) */
  475.  
  476.         Push( operator );
  477.         Compile_Object( Top( 1 ));
  478.         Push( Value_Register );    /* operator on stack */
  479.  
  480.         Push( Rest( Top( 2 ) ));
  481.         Compile_Arguments();
  482.         Push( Value_Register ); /* arguments on stack */
  483.  
  484.         Make_Apply();
  485.     }
  486.     Pop(1);    /* Original form */
  487. }
  488.  
  489.  
  490.  
  491.  
  492. Private void Compile_Arguments()
  493. {
  494.     /* Compile the list of arguments (or clauses) that are atop stack;
  495.        leave the resulting (compiled) list in Value_Register.
  496.     */
  497.  
  498.     if ( !Is_List( Top( 1 )) )
  499.     {
  500.         Display_Error( "Syntax : list expected by compiler: ", Top(1) );
  501.     }
  502.     else if ( Top( 1 ) == Nil )
  503.     {
  504.         Value_Register = Nil;
  505.     }
  506.     else  /* A non-empty list */
  507.     {
  508.         Push( First( Top( 1 )));
  509.         Compile_Object( Top( 1 ));
  510.         Push( Value_Register );    /* First (compiled) element on stack */
  511.  
  512.         Push( Rest( Top( 2 )));    
  513.         Compile_Arguments();
  514.         Push( Value_Register ); /* Rest of (compiled) list on stack */
  515.  
  516.         Make_Pair();        /* Compiled list in Value_Register */
  517.     }
  518.     Pop( 1 );  /* Original form */
  519. }
  520.  
  521.  
  522.  
  523. Public void Compile_Symbol()
  524. {
  525.     Lookup_Address( Top(1), Environment_Register );
  526.     Pop(1);
  527. }
  528.  
  529.  
  530.  
  531. Private void Lookup_Address(symbol, env)
  532.  
  533.     Object symbol, env;
  534. {
  535.     Integer    frame , displacement;
  536.  
  537.     if (! Is_Symbol(symbol) )
  538.     {
  539.         Panic("Lookup_Address called with bad symbol argument");
  540.     }
  541.     else if ( ! Is_Environment_Frame(env) )
  542.     {
  543.         Panic( "Lookup_Address called with bad environment argument" );
  544.     }
  545.  
  546.     frame = 0;
  547.     while (env != The_Global_Environment)
  548.     {
  549.         for (displacement = 0; displacement < 
  550.                     Get_Environment_Frame_Size(env);  displacement++)
  551.         {
  552.             if (Get_Environment_Frame_Binding_Symbol
  553.                             (env,displacement) == symbol)
  554.             {
  555.                 Make_Local_Variable(symbol,frame,displacement);
  556.                 return;
  557.             }
  558.         }
  559.         env = Get_Environment_Frame_Previous( env );
  560.         frame++;
  561.     }
  562.  
  563.     Make_Global_Variable( symbol );
  564. }
  565.  
  566. Private Object Scanned_Internal_Defns( body )
  567.  
  568.     Object body; /* not yet compiled */
  569. {
  570.     if ( Is_Pair(body) )
  571.     {
  572.  
  573.         Object clause = First( body );
  574.  
  575.         if  ( Is_Pair( clause ) && First( clause ) == DEFINE_Symbol )
  576.         {
  577.             clause = Second( clause );
  578.             Push( Is_Symbol( clause ) ? clause :
  579.                   Is_Pair( clause ) && Is_Symbol( First(clause) ) 
  580.                 ? First( clause ): The_Undefined_Symbol );
  581.             Push( Scanned_Internal_Defns( Rest( body ) ) );
  582.             Make_Pair();
  583.             return ( Value_Register );
  584.         }
  585.     }
  586.     return ( Nil );
  587. }
  588.