CSC 374: Computer Systems II: 2017 Winter
Assignment #2

Last Modified 2017 January 23

Purpose:

To go over:

  • Processes
  • Signals

Computing

Please ssh into one of the following:

  • 140.192.36.184
  • 140.192.36.185
  • 140.192.36.186
  • 140.192.36.187

or use your own Linux machine.

Please submit a .zip file (not .7z or any other non-standard compression!) file of your header file and a .txt/.pdf/.doc/.odt file containing your answer to the questions.

Overview:

This application has 3 programs that ask the user to guess 4 yes/no (or 0/1) questions.

  • When the user guesses one bit correctly, they are go on to guess the next
  • When the user guesses one bit incorrectly, they have to go back to the beginning of the sequence and enter the first bit again

Example output:

The correct sequence is 0-0-1-1

$ ./launcher  (The answer is 12) Starting from the beginning: What would you like your next guess to be: 0 or 1? 0  (lucky guess of 1st bit) position 0: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 0  (lucky guess of 2nd bit) position 1: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 0  (Oops!  This bit is wrong!) position 2: userBit 0, correctBit 1 Oops!  That was wrong.  Please restart from the beginning.   Re-starting from the beginning: What would you like your next guess to be: 0 or 1? 0  (We know this bit from our earlier correct guess) position 0: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 0  (We know this bit from our earlier correct guess) position 1: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 1  (We know this bit from our earlier incorrect guess, must be opposite) position 2: userBit 1, correctBit 1 Yay!  That was right! What would you like your next guess to be: 0 or 1? 0  (Oops!  This last bit is wrong!) position 3: userBit 0, correctBit 1 Oops!  That was wrong.  Please restart from the beginning.   Re-starting from the beginning: What would you like your next guess to be: 0 or 1? 0  (We know this bit from our earlier correct guess) position 0: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 0  (We know this bit from our earlier correct guess) position 1: userBit 0, correctBit 0 Yay!  That was right! What would you like your next guess to be: 0 or 1? 1  (We know this bit from our earlier incorrect guess) position 2: userBit 1, correctBit 1 Yay!  That was right! What would you like your next guess to be: 0 or 1? 1  (We know this bit from our earlier incorrect guess) position 3: userBit 1, correctBit 1 answerer finished  Congratulations!  You found it! guesser finished launcher finished

The user has a time limit (NUM_SECONDS seconds) to find this pattern, or else the game ends automatically:

$ ./launcher  (The answer is 1) What would you like your next guess to be: 0 or 1?   (I do not type anything and wait NUM_SECONDS seconds) answerer finished Oh no!  The time is up! guesser finished launcher finished       

Please finish this single application implemented with 3 programs:

  1. launcher.c
    1. The program will have 3 global vars: answererPidguesserPid, and shouldRunshouldRun should be initialized to 1.
    2. Its main() install two signal handlers: one for SIGALRM and one for SIGCHLD.
      • The SIGALRM handler will tell the two child processes to stop by sending them TIME_OVER_SIGNAL. It also sets shouldRun to 0.
      • The SIGCHLD does a waitpid() in a loop to get all finished children. It also sets shouldRun to 0.
    3. After installing the signal handlers, main() launches first the answering program, and then the guessing program. 
      To when launching the answering program put the child pid in 
      answererPid and have the child run the string constantANSWERER_PROGNAME
      To when launching the guessing program put the child pid in 
      guesserPid and have the child run the string constantGUESSER_PROGNAME. The guesser program must be told the process id of the answering process. Turn that to the string line[] with the following code:

charline[LINE_LEN];  snprintf(line,LINE_LEN,"%d",answererPid);     

Be sure to pass line to the guesser.

    1. Then main() sets its self up to receive SIGALRM in NUM_SECONDS seconds.
    2. Lastly main() just does the following:

while  (shouldRun)   sleep(1);  sleep(1); sleep(1);  printf("launcher finished\n"); return(EXIT_SUCCESS);     

  1. guesser.c
    1. guesser.c should also have a global int shouldRun variable initialized to 1.
    2. Its main() should make sure it has a command line argument (exiting with EXIT_FAILURE if not). It should that argument is the process id of the answerer. Convert it from a string to an integer and hold on to its value.
    3. Then, main() should install 4 signal handler:
      • The handler for TIME_OVER_SIGNAL announces that the time is up and sets shouldRun to 0.
      • The handler for WIN_SIGNAL announces that the user won and sets shouldRun to 0.
      • The handler for CORRECT_SIGNAL announces that the user got their last guess correct.
      • The handler for INCORRECT_SIGNAL announces that the user got their last guess wrong, and should start again from the beginning.

NOTE: Perhaps you can make the same handler handle both CORRECT_SIGNAL and INCORRECT_SIGNAL.

    1. In a while(shouldRun) loop, allow the user to enter their next guess. If they enter 0 send the answerer ZERO_SIGNAL. If they enter 1 send the answerer ONE_SIGNAL. At after sending the signal, do a sleep(1) to give the answerer time to respond.
    2. After the loop just do:

printf("guesser finished\n"); return(EXIT_SUCCESS);     

  1. assign2Headers.h

Just copy-and-paste the following:

/*-------------------------------------------------------------------------*  

*------*  

*---assign2Headers.h---*  

*------*  

*---    This file includes standard headers and declares constants---*  

*---common to the assignment 2 C programs.---*  

*------*  

*--------------------------------------*  

*------*  

*---Version 1a2017 January 9Joseph Phillips---*  

*------*  

*-------------------------------------------------------------------------*/  

//---Common standard header files---//  

#include<stdlib.h> 

#include<stdio.h> 

#include<string.h> 

#include<signal.h> 

#include<sys/types.h> 

#include<sys/wait.h> 

#include<unistd.h>   

//---Common constants:---//  

#define ZERO_SIGNAL SIGUSR1  

#define ONE_SIGNAL SIGUSR2  

#define CORRECT_SIGNAL SIGUSR1  

#define INCORRECT_SIGNAL SIGUSR2  

#define WIN_SIGNAL SIGINT  

#define TIME_OVER_SIGNAL SIGTERM  

#define GUESSER_PROGNAME "guesser"  

#define ANSWERER_PROGNAME "answerer"  

#define LINE_LEN 256  

 

#define NUM_SECONDS 30

  1. answerer.c

Just copy-and-paste the following:

 

/*-------------------------------------------------------------------------*  

*------*  

*---answerer.c---*  

*------*  

*---    This file defines the answerer program for assignment #2.---*  

*------*  

*--------------------------------------*  

*------*  *---Version 1a2017 January 9Joseph Phillips---*  

*------*  

*-------------------------------------------------------------------------*/  

//---Inclusion of header files---//  

#include "assign2Headers.h"   

 

//---Definition of constants:---//  

#define PATTERN_LEN4   

//---Definition of global vars:---//  

intanswer;  

intnumCorrect= 0;  

intshouldRun= 1;   

//---Definition of global fncs:---//  

voidtimeUpHandler(int sig ) {   shouldRun= 0; }   

 

voidguessHandler(intsig,  siginfo_t*infoPtr,  void *dataPtr ) {   

inttoSendBack;   

intuserBit= (sig == ONE_SIGNAL);   

intcorrectBit= ((answer >> numCorrect) & 0x1);   

intisCorrect= (correctBit == userBit);    

printf("position %d: userBit %d, correctBit %d\n",  numCorrect,userBit,correctBit );    

if  (isCorrect)   {     

numCorrect++;      

if  (numCorrect >= PATTERN_LEN)       toSendBack = WIN_SIGNAL;     else       toSendBack = CORRECT_SIGNAL;   

}   else   {     

numCorrect= 0;     

toSendBack= INCORRECT_SIGNAL;   

}    

kill(infoPtr->si_pid,toSendBack); 

}   

 

intmain(intargc,  char*argv[] ) {   

//  I.  Application validity check:    

//  II.  Run program:   

//  II.A.  Initialize random number generator and choice:   

srand(getpid());    

answer= rand() % (1 << PATTERN_LEN);  

printf("(The answer is %d)\n",answer);    

//  II.B.  Install signal handlers:   

struct sigactionact;    

memset(&act,'\0',sizeof(act));   

act.sa_handler= timeUpHandler;   

sigaction(TIME_OVER_SIGNAL,&act,NULL);    

act.sa_flags= SA_SIGINFO;   

act.sa_sigaction= guessHandler;   

sigaction(ZERO_SIGNAL,&act,NULL);   

sigaction(ONE_SIGNAL,&act,NULL);    

//  II.C.  Hand out while game still active:   

while  ( (numCorrect < PATTERN_LEN)  &&  shouldRun )     sleep(1);    

//  III.  Finished, return answer:   

printf("answerer finished\n");   

return(EXIT_SUCCESS); 

 

}

/*-------------------------------------------------------------------------*
 *---																	---*
 *---							luncher.c					---*/
#include	"assign2Headers.h";

	int answererPid;
	int guesserPid;
	int shouldRun = 1;
	
	void  INThandler1(int sig)
	{
		 char  c;
		 signal(sig, SIG_IGN); //??????????????? ignore other signals
		 int r = kill (answererPid, TIME_OVER_SIGNAL);
		 int r2 = kill (guesserPid, TIME_OVER_SIGNAL);
		 shouldRun=0;
		 exit(0);

	}

	void  INThandler2(int sig)
	{
		int s;
		while( (pid=waitpid(1,&s,WNOHANG)) > 0)  //WNOHANG : return immediately if no child has exited.
			{}
		shouldRun=0;		
	}
	
	int	main (int argc, char* argv[]){

		// Signal 1 : SIGALRM
		struct sigaction psa1;
		memset($psa1,'\0', sizeof(struct sigaction));
		sigemptyset(&psa1.sa_mask);
		
		psa1.flags = SA_SIGINFO | SA_RESTART;
		psa1.sa_sigaction = INThandler1;
		sigaction(SIGALRM, &psa1, NULL);
		alarm(NUM_SECONDS);
		
		// Signal 2 : SIGCHLD

		struct sigaction psa2;
		memset($psa2,'\0', sizeof(struct sigaction));
		sigemptyset(&psa2.sa_mask);	
		psa2.flags = SA_SIGINFO | SA_RESTART;
		psa2.sa_sigaction = INThandler2;		
		sigaction(SIGCHLD, &psa2, NULL);
		
		
		char	line[LINE_LEN]; 
		
		if (fork() == 0){
            guesserPid = getpid();
			snprintf(line,LINE_LEN,"%d",guesserPid);    		
			if (guesserPid=execl("./guesser", GUESSER_PROGNAME, (char*) NULL)==-1){
				printf("Cannot start guesser!\n");
				exit(0);
				}
			else {
					printf("Guesser is started!\n");
					exit(0);
				}	
			shouldRun=0;
		}
		
		if (fork() == 0){
				answererPid = getpid(); 
				snprintf(line,LINE_LEN,"%d",answererPid);		
				if (execl("./answerer", ANSWERER_PROGNAME, (char*) NULL)==-1){   
				printf("Cannot start answer!\n");
				exit(0);
				}
			else 
				{ 	printf("Answer is started!\n");
					exit(0);
				}		
			shouldRun=0;
			
				
		}
		
		

		while  (shouldRun){
			sleep(1);
		}
		sleep(1);
		sleep(1);

		printf("launcher finished\n");
		return(EXIT_SUCCESS);
	}
/*-------------------------------------------------------------------------*
 *---																	---*
 *---							guesser.c.]					---*/

#include "assign2Headers.h";

int shouldRun = 1;

int	main (int argc, char* argv[]){

	struct sigaction	act;
	char guess;

	memset(&act,'\0',sizeof(act));
	act.sa_handler	= timeUpHandler;
	sigaction(TIME_OVER_SIGNAL,&act,NULL);

	act.sa_flags		= SA_SIGINFO;
	act.sa_sigaction	= winHandler;
	sigaction(WIN_SIGNAL,&act,NULL);
  
	act.sa_sigaction	= correctHandler;
	sigaction(CORRECT_SIGNAL,&act,NULL);

	act.sa_sigaction	= incorrectHandler;
	sigaction(INCORRECT_SIGNAL,&act,NULL);  
	int r;
	
	int pid = fork();
	while  (shouldRun){
		printf("What would you like your next guess to be: 0 or 1?");
		scanf("%d", &guess);
	    if (guess == '0') {
			r = kill (pid, ZERO_SIGNAL);
		} else if (guess == '1'){
			r = kill (pid, ONE_SIGNAL);
		} else {}		
		sleep(1);
		}

	sleep(1);
	sleep(1);

	printf("guesser finished\n");
	return(EXIT_SUCCESS);
}

void  timeUpHandler(int sig, siginfo_t* infoPtr, void* dataPtr)
{
	 printf("Oh no!  The time is up!");
	 shouldRun=0;
}

void  winHandler(int sig, siginfo_t* infoPtr, void* dataPtr)
{
	 printf("Congratulations!  You found it!\n");
	 shouldRun=0;
}

void  correctHandler(int sig, siginfo_t* infoPtr, void* dataPtr)
{
	printf("Yay!  That was right!\n");
}

void  incorrectHandler(int sig, siginfo_t* infoPtr, void* dataPtr)
{
	printf("Oops!  That was wrong.  Please restart from the beginning.\n");

}
void  timeUpHandler(int sig)
{
	 shouldRun=0;
	 printf("Oh no!  The time is up!");
}

void  winHandler(int sig)
{
	 shouldRun=0;
	 printf("Congratulations!  You found it!\n");
}

void  correctHandler(int sig)
{
	//shouldRun=0;
	printf("Yay!  That was right!\n");
}

void  incorrectHandler(int sig)
{
	printf("Oops!  That was wrong.  Please restart from the beginning.\n");
	//shouldRun=0;
}

/*-------------------------------------------------------------------------*
 *---																	---*
 *---							assign2Headers.h						---*
 *---																	---*
 *---	    This file includes standard headers and declares constants	---*
 *---				common to the assignment 2 C programs.				---*
 *---																	---*
 *---	----	----	----	----	----	----	----	----	---*
 *---																	---*
 *---		Version 1a		2017 January 9			Joseph Phillips		---*
 *---																	---*
 *-------------------------------------------------------------------------*/
//---		Common standard header files				---//
#include	<stdlib.h>
#include	<stdio.h>
#include	<string.h>
#include	<signal.h>
#include	<sys/types.h>
#include	<sys/wait.h>
#include	<unistd.h>
//---		Common constants:					---//
#define		ZERO_SIGNAL		SIGUSR1
#define		ONE_SIGNAL		SIGUSR2
#define		CORRECT_SIGNAL		SIGUSR1
#define		INCORRECT_SIGNAL	SIGUSR2
#define		WIN_SIGNAL		SIGINT
#define		TIME_OVER_SIGNAL	SIGTERM
#define		GUESSER_PROGNAME	"guesser"
#define		ANSWERER_PROGNAME	"answerer"
#define		LINE_LEN		256
#define		NUM_SECONDS		30

/*-------------------------------------------------------------------------*
 *---																	---*
 *---							answerer.c								---*
 *---																	---*
 *---	    This file defines the answerer program for assignment #2.	---*
 *---																	---*
 *---	----	----	----	----	----	----	----	----	---*
 *---																	---*
 *---		Version 1a		2017 January 9		Joseph Phillips			---*
 *---																	---*
 *-------------------------------------------------------------------------*/
//---		Inclusion of header files				---//
#include	"assign2Headers.h";
//---		Definition of constants:				---//
#define		PATTERN_LEN	4
//---		Definition of global vars:				---//
int		answer;
int		numCorrect	= 0;
int		shouldRun	= 1;
//---		Definition of global fncs:				---//
void timeUpHandler(int sig){
	shouldRun	= 0;
}
void guessHandler(int sig, siginfo_t* infoPtr, void* dataPtr){
  int	toSendBack;
  int	userBit = (sig == ONE_SIGNAL);
  int	correctBit = ((answer >> numCorrect) & 0x1);
  int	isCorrect = (correctBit == userBit);

  printf("position %d: userBit %d, correctBit %d\n", numCorrect,userBit,correctBit);

  if  (isCorrect){
    numCorrect++;

    if  (numCorrect >= PATTERN_LEN)
      toSendBack = WIN_SIGNAL;
    else
      toSendBack = CORRECT_SIGNAL;
  }else{
    numCorrect	= 0;
    toSendBack	= INCORRECT_SIGNAL;
  }

  kill(infoPtr->si_pid,toSendBack);
}


int	main (int argc, char* argv[]){
  //  I.  Application validity check:

  //  II.  Run program:
  //  II.A.  Initialize random number generator and choice:
	srand(getpid());

	answer	= rand() % (1 << PATTERN_LEN);

	printf("(The answer is %d)\n",answer);

  //  II.B.  Install signal handlers:
  struct sigaction	act;

  memset(&act,'\0',sizeof(act));
  act.sa_handler	= timeUpHandler;
  sigaction(TIME_OVER_SIGNAL,&act,NULL);

  act.sa_flags		= SA_SIGINFO;
  act.sa_sigaction	= guessHandler;
  sigaction(ZERO_SIGNAL,&act,NULL);
  sigaction(ONE_SIGNAL,&act,NULL);

  //  II.C.  Hand out while game still active:
  while  ( (numCorrect < PATTERN_LEN)  &&  shouldRun )
    sleep(1);

  //  III.  Finished, return answer:
  printf("answerer finished\n");
  return(EXIT_SUCCESS);
}
http://stackoverflow.com/questions/42128543/assignment-from-incompatible-pointer-type-how-to-fix
 sealed trait Expr
  case class CstI (n : Int)                                           extends Expr
  case class Var (nm : String)                                        extends Expr
  case class Prim (nm : String, e1 : Expr, e2 : Expr)                 extends Expr
  case class Call (nm : String, es : List[Expr])                      extends Expr
  case class Quotaion (nm1 : String, nm2 : String)                    extends Expr // quotation
 

  sealed trait Stmt
  case class Asgn (nm : String, e : Expr)                         extends Stmt //assignment
//  case class Definition (v : String, e : Expr)       extends Stmt // definition 
  case class If (s1 : Stmt, e : Expr,  s2 : Stmt)                 extends Stmt
  case class Block (ss : List[Stmt])                              extends Stmt
  case class Print (e : Expr)                                     extends Stmt
  case class Return (e : Expr)                                    extends Stmt

val keywords : List[String] = List ("if", "else", "print")
    val multDiv : Parser[Expr] = P (
      ((("*" | "/").! ~ atExpr ~ atExpr).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val addSub : Parser[Expr] = P (
      ((("+" | "-" | "%").! ~ multDiv ~ multDiv).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val gtLtGeLeExpr : Parser[Expr] = P (
      (((">" | "<" | ">=" | "<=").! ~ addSub ~ addSub).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val eqNeExpr : Parser[Expr] = P (
      ((("=" | "<>").! ~ gtLtGeLeExpr ~ gtLtGeLeExpr).rep.map (s => s.toList)).map (foldAssocLeft)
    )
  
 val stmt : Parser[Stmt] = P (
      ("define" ~ ident ~ expr ~ ).map { case (nm, e) => Asgn (nm, e) } |
      ("if" ~ "(" ~ expr ~ ")" ~ stmt ~ "else" ~ stmt ).map { case (s1, e, s2) => If (e, s1, s2) } |
      ("(" ~ stmt.rep ~ ")").map { case ss => Block (ss.toList) } |
      ("print" ~ "(" ~ expr ~ ")" ).map { case (e) => Print (e) } |
      ("return" ~ expr).map { case (e) => Return (e) }
    )
   case Prim (op, e1, e2) => {
        val insts1 = compileExpr (e1, env, fenv) 
        val insts2 = compileExpr (e2, env, fenv)
        val push = "\tpushq\t%rax\n"
        def pop (reg : String) = "\tpopq\t%%%s\n".format (reg)
        val instsOp : String = op match {
          case  "+" => "\taddq\t%rbx, %rax\n"
          case  "-" => "\tsubq\t%rbx, %rax\n"
          case  "*" => "\timulq\t%rbx, %rax\n"
          case  "=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets ZF if ((rax-rbx) = 0) as signed, i.e., (rax = rbx)
            "\tsete\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if ZF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
          // case "<>" => b2i (i1 != i2) 
          case  "<" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsets\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  ">" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetg\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  "<=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetle\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  ">=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetge\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
          // case  ">" => b2i (i1 > i2) 
          // case "<=" => b2i (i1 <= i2) 
          // case ">=" => b2i (i1 >= i2) 
          case   _ => throw new RuntimeException ("unknown primitive " + op)
        }
        insts1 +
        insts2 +
        pop ("rbx") +
        pop ("rax") +
        instsOp + 
        push
      }
http://web.itu.edu.tr/kesgin/mul06/intel/
package csp.ch08

// From SBT: ~run-main csp.ch08.NaiveCodeGenFunc

// Based on the parser/interpreter in directory Imp from the Sestoft source code, but adds code generation for x86-64 AND function definition/calls

// Obvious extensions:
// - Add negative numbers (so test05.naive can switch from "0-2" to "-2".
// - Allow function calls (more generally expression) as statements so that we do not need to assign to a "dummy" variable.
// - Add local variable declarations inside blocks.  Environments are extended after local variable declarations.
// - Add arrays of integers as a datatype.  Heap allocate with manual memory management.


object NaiveCodeGenFunc {

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Abstract Syntax
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  sealed trait Expr
  case class CstI (n : Int)                                           extends Expr
  case class Var (nm : String)                                        extends Expr
  case class Prim (nm : String, e1 : Expr, e2 : Expr)                 extends Expr
  case class Call (nm : String, es : List[Expr])                      extends Expr
 // case class Quotaion (nm1 : String, nm2 : String)                    extends Expr // quotation
 

  sealed trait Stmt
  case class Asgn (nm : String, e : Expr)                         extends Stmt //assignment
  case class Define (v : String, e : Expr)       extends Stmt // definition 
  case class If (s1 : Stmt, e : Expr,  s2 : Stmt)                 extends Stmt
  case class Block (ss : List[Stmt])                              extends Stmt
  case class Print (e : Expr)                                     extends Stmt
  case class Return (e : Expr)                                    extends Stmt
  case class Quotaion (nm1 : String, nm2 : String)                extends Stmt // quotation

  case class FuncDef (nm : String, params : List[String], body : Stmt)

  case class Program (funs : List[FuncDef], main : Stmt)

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Parsing
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  def foldAssocLeft (p : (Expr, List[(String,Expr)])) : Expr = {
    p match {
      case (e1, Nil)              => e1
      case (e1, (op, e2) :: rest) => foldAssocLeft (Prim (op, e1, e2), rest)
    }
  }

  object MyParsersNoWhitespace {
    import fastparse.all._

    val digits : Parser[Int] = P (CharIn ('0' to '9').rep (1).!).map (s => s.toInt)
    val integer : Parser[Expr] = P (digits.map (n => CstI (n)))

    val keywords : List[String] = List ("if", "else", "print")
    val alpha : Parser[String] = P ((CharIn ('A' to 'Z') | CharIn ('a' to 'z')).!)
    val ident : Parser[String] = P ((alpha ~ (alpha | CharIn ('0' to '9')).rep (0)).!).filter (s => !keywords.contains (s))
    val variable : Parser[Expr] = P (ident.map (s => Var (s)))
  }

  object MyParsers {
    val White = fastparse.WhitespaceApi.Wrapper {
      import fastparse.all._
      NoTrace (CharIn (" \n").rep)
    }

    import fastparse.noApi._
    import White._

    import MyParsersNoWhitespace._

    val atExpr : Parser[Expr] = P (
      integer | 
      (ident ~ ("(" ~ expr.rep (sep = ",").map (s => s.toList) ~ ")").?).map {
        case (nm, None)      => Var (nm)
        case (nm, Some (es)) => Call (nm, es)
      } | 
      ("(" ~/ expr ~ ")") 
    )
    val multDiv : Parser[Expr] = P (
      ((("*" | "/").! ~ atExpr ~ atExpr).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val addSub : Parser[Expr] = P (
      ((("+" | "-" | "%").! ~ multDiv ~ multDiv).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val gtLtGeLeExpr : Parser[Expr] = P (
      (((">" | "<" | ">=" | "<=").! ~ addSub ~ addSub).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val eqNeExpr : Parser[Expr] = P (
      ((("=" | "<>").! ~ gtLtGeLeExpr ~ gtLtGeLeExpr).rep.map (s => s.toList)).map (foldAssocLeft)
    )
    val expr : Parser[Expr] = P (eqNeExpr)

    val stmt : Parser[Stmt] = P (
      ("define" ~ ident ~ expr ~ ).map { case (nm, e) => Asgn (nm, e) } |
	  ("set!" ~ ident ~ expr ~ ).map { case (nm, e) => Define (nm, e) } |
	  ("quote!" ~ expr ~ ).map { case (e) => Var(e) } |
      ("if" ~ "(" ~ expr ~ ")" ~ stmt ~ "else" ~ stmt ).map { case (s1, e, s2) => If (e, s1, s2) } |
      ("(" ~ stmt.rep ~ ")").map { case ss => Block (ss.toList) } |
      ("print" ~ "(" ~ expr ~ ")" ).map { case (e) => Print (e) } |
      ("return" ~ expr).map { case (e) => Return (e) }
    )

    val funcdef : Parser[FuncDef] = P (
      ("def" ~ ident ~ "(" ~ ident.rep (sep=",").map (s => s.toList) ~ ")" ~ stmt).map { case (nm, params, body) => FuncDef (nm, params, body) }
    )

    val program : Parser[Program] = P (
      (funcdef.rep.map (s => s.toList) ~ "main" ~ stmt).map { case (funcdefs, body) => Program (funcdefs, body) }
    )

    val start : Parser[Program] = P (program ~ End)
  }

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Pretty printing
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  def ppExpr (e : Expr) : String = {
    e match {
      case CstI (i)                     => i.toString
      case Var (x)                      => x
      case Prim (op, e1, e2)            => "(%s %s %s)".format (ppExpr (e1), op, ppExpr (e2))
      case Call (nm, es)                => "(%s (%s))".format (nm, es.map (ppExpr).mkString (", "))
    }
  }

  def ppBlock (indent : String, s : Stmt) : String = {
    val newIndent = indent + "  "
    s match {
      case Block (ss) => {
        val sb = new StringBuilder
        for (s  {
        "%s".format (ppStmt (newIndent, s))
      }
    }
  }

  def ppStmt (indent : String, s : Stmt) : String = {
    val newIndent = indent + "  "
    s match {
      case Asgn (nm, e)           => 
        "%s%s := %s;\n".format (indent, nm, ppExpr (e))
	  case Define (nm, e)           => 
        "%s%s := %s;\n".format (indent, nm, ppExpr (e))	
      case If (e, s1, s2)         => 
        "%sif (%s) {\n%s%s} else {\n%s%s}\n".format (indent, ppExpr (e), ppBlock (indent, s1), indent, ppBlock (indent, s2), indent)
      case Block (ss) => {
        "%s{\n%s%s}\n".format (indent, ppBlock (indent, s), indent)
      }
      case For (nm, low, high, s) => {
        "%sfor (%s := %s to %s) {\n%s%s}\n".format (indent, nm, ppExpr (low), ppExpr (high), ppBlock (indent, s), indent)
      }
      case While (e, s)           => 
        "%swhile (%s) {\n%s%s}\n".format (indent, ppExpr (e), ppBlock (indent, s), indent)
      case Print (e)              => 
        "%sprint (%s);\n".format (indent, ppExpr (e))
      case Return (e)             => 
        "%sreturn (%s);\n".format (indent, ppExpr (e))
    }
  }

  def ppFuncDef (f : FuncDef) : String = {
    "def %s (%s)\n%s".format (f.nm, f.params.mkString (", "), ppStmt ("", f.body))
  }

  def ppProgram (p : Program) : String = {
    p.funs.map (f => ppFuncDef (f)).mkString ("\n") + ppStmt ("", p.main)
  }

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Code Generation
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  type Env = Map[String,String]
  type FuncEnv = Map[String,FuncDef]

  val emptyEnv : Env = Map.empty

  var labelCounter : Int = 0
  def newLabel () : String = {
    labelCounter = labelCounter + 1
    "lab%03d".format (labelCounter)
  }

  // Generate x86-64 assembly to evaluate e.
  // Result is at the top of the stack.
  // The following registers may be changed by the generated assembly language: %rax, %rbx, %rsp, %rip
  def compileExpr (e : Expr, env : Env, fenv : FuncEnv) : String = {
    e match {
      case CstI (i)           => 
        "\tpushq\t$%d\n".format (i)
      case Var (x)            => 
        env.get (x) match {
          case None => throw new RuntimeException ("unable to find variable %s in environment".format (x))
          case Some (lab) => 
            "\tpushq\t%s\n".format (lab)
        }
      case Prim (op, e1, e2) => {
        val insts1 = compileExpr (e1, env, fenv) 
        val insts2 = compileExpr (e2, env, fenv)
        val push = "\tpushq\t%rax\n"
        def pop (reg : String) = "\tpopq\t%%%s\n".format (reg)
        val instsOp : String = op match {
          case  "+" => "\taddq\t%rbx, %rax\n"
          case  "-" => "\tsubq\t%rbx, %rax\n"
          case  "*" => "\timulq\t%rbx, %rax\n"
          case  "=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets ZF if ((rax-rbx) = 0) as signed, i.e., (rax = rbx)
            "\tsete\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if ZF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
          // case "<>" => b2i (i1 != i2) 
          case  "<" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsets\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  ">" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetg\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  "<=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetle\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
		  case  ">=" => {
            "\tcmpq\t%rbx, %rax\n" +    // sets SF if ((rax-rbx) < 0) as signed, i.e., (rax < rbx)
            "\tsetge\t%al\n" +           // sets low-order byte (%al) of %rax to 1 if SF is set, otherwise to 0
            "\tmovzbl\t%al, %eax\n"     // extends %al to %rax (recall that assignment to a 32-bit register clears the upper 32-bits of the corresponding 64-bit register)
          }
          // case  ">" => b2i (i1 > i2) 
          // case "<=" => b2i (i1 <= i2) 
          // case ">=" => b2i (i1 >= i2) 
          case   _ => throw new RuntimeException ("unknown primitive " + op)
        }
        insts1 +
        insts2 +
        pop ("rbx") +
        pop ("rax") +
        instsOp + 
        push
      }
      case Call (nm, es) => {
        es.reverse.map (e => compileExpr (e, env, fenv)).mkString +
        "\tcall\t%s\n".format (nm) + 
        "\taddq\t$%d, %%rsp\n".format (es.length * 8) +
        "\tpushq\t%rax\n"
      }
    }
  }

  def compileAll (prog : Program, env : Env, fenv : FuncEnv) : String = {
    header () + 
    compileFunc (FuncDef ("main", Nil, prog.main), env, fenv) + 
    "\n" +
    prog.funs.map (fd => compileFunc (fd, env, fenv)).mkString ("\n") + 
    footer (env)
  }

  def header () : String = {
    ""
  }

  def footer (env : Env) : String = {
    "\n" +
    "\t.section .rodata\n" + 
    ".output:\n" + 
    "\t.string \"%d\\n\"\n" +
    "\n" +
    (for ((nm1, _)  {
        env.get (nm) match {
          case None => throw new RuntimeException ("unable to find variable %s in environment".format (nm))
          case Some (lab) => 
            ppStmt ("// ", s) + 
            compileExpr (e, env, fenv) + 
            "\tpopq\t%rax\n" +
            "\tmovq\t%%rax, %s\n".format (lab)
        }
      }
      case If (e, s1, s2)          => 
        val label1 = newLabel ()
        val label2 = newLabel ()
        val label3 = newLabel ()
        "// %s\n".format (ppExpr (e)) + 
        compileExpr (e, env, fenv) +
        "\tpopq\t%rax\n" + 
        "\ttestq\t%rax, %rax\n" + 
        "\tjne\t%s\n".format (label1) +
        "\tjmp\t%s\n".format (label2) +
        "%s:\n".format (label1) +
        compileStmt (s1, env, fenv) +
        "\tjmp\t%s\n".format (label3) +
        "%s:\n".format (label2) +
        compileStmt (s2, env, fenv) +
        "%s:\n".format (label3) 
      case Block (ss)              => {
        def loop (ss2 : List[Stmt]) : String = {
          ss2 match {
            case Nil       => ""
            case s2 :: ss3 => compileStmt (s2, env, fenv) + loop (ss3)
          }
        }
        loop (ss)
      }
     
      case Print (e)               => {
        ppStmt ("// ", s) + 
        compileExpr (e, env, fenv) +
        "\tpopq\t%rsi\n" +
        "\tmovl\t$.output, %edi\n" + 
        "\tmovl\t$0, %eax\n" +
        "\tcall\tprintf\n"
      }
      case Return (e)               => {
        ppStmt ("// ", s) + 
        compileExpr (e, env, fenv) +
        "\tpopq\t%rax\n" +
        "\tpopq\t%rbp\n" + 
        "\tret\n"
      }
    }
  }

  def findVarsExpr (e : Expr) : List[String] = {
    e match {
      case CstI (i)           => Nil
      case Var (x)            => List (x)
      case Prim (op, e1, e2)  => findVarsExpr (e1) ::: findVarsExpr (e2)
      case Call (nm, es)      => es.flatMap (findVarsExpr)
    }
  }

  def findVarsStmt (s : Stmt) : List[String] = {
    s match {
      case Asgn (nm, e)            => nm :: findVarsExpr (e)
      case If (e, s1, s2)          => findVarsExpr (e) ::: findVarsStmt (s1) ::: findVarsStmt (s2)
      case Block (ss)              => {
        def loop (ss2 : List[Stmt]) : List[String] = {
          ss2 match {
            case Nil       => Nil
            case s2 :: ss3 => findVarsStmt (s2) ::: loop (ss3)
          }
        }
        loop (ss)
      }
      case For (nm, low, high, s)  => {
        nm :: findVarsExpr (low) ::: findVarsExpr (high) ::: findVarsStmt (s)
      }
      case While (e, s)            => {
        findVarsExpr (e) ::: findVarsStmt (s)
      }
      case Print (e)               => {
        findVarsExpr (e)
      }
      case Return (e)              => {
        findVarsExpr (e)
      }
    }
  }

  def findVars (s : Stmt) : List[String] = {
    findVarsStmt (s).toSet.toList.sortWith ((s1,s2) => s1 < s2)
  }

  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Testing
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

  // (* Example programs *)

  val ex1 : Stmt = {
    Block (
      List (
        Asgn (
          "sum", 
          CstI (0)),
        For (
          "i", 
          CstI (0), 
          CstI (100), 
          Asgn (
            "sum", 
            Prim ("+", Var ("sum"), Var ("i"))
          )),
        Print (Var ("sum"))
      )
    )
  }

  val ex2 : Stmt = {
    Block (
      List (
        Asgn (
          "i", 
          CstI (1)
        ),
        Asgn (
          "sum", 
          CstI (0)
        ),
        While (
          Prim ("<", Var ("sum"), CstI (10000)),
          Block (
            List (
              Print (Var ("sum")),
              Asgn (
                "sum", 
                Prim ("+", Var ("sum"), Var ("i"))
              ),
              Asgn (
                "i", 
                Prim ("+", CstI (1), Var ("i"))
              )
            )
          )
        ),
        Print (Var ("i")),
        Print (Var ("sum"))
      )
    )
  }

  import fastparse.all.{Parsed,Parser}

  def readFile (filename : String) : String = {
    val source : scala.io.BufferedSource = io.Source.fromFile (filename)
    try source.getLines.mkString ("\n") finally source.close ()
  }

  def invokeAssemblerLinker (asmFilename : String) : Unit = {
    import scala.sys.process.{Process}
    val pb = Process (List ("gcc", "-o", asmFilename.replace (".s", ""), asmFilename))
    import scala.language.postfixOps
    val result : String = (pb !!)
    println ("Running assembler: %s".format (result))
  }

  def compile (prog : Program, filename: String) : Unit = {
    val fenv : FuncEnv = (for (fd  f.body)); v  {
        println ("Successfully parsed file \"%s\".\nResult is %s.\nIndex is %d.".format (filename, prog, successIndex))
        // println ("Pretty printing:")
        // print (ppStmt ("  ", stmt))
        compile (prog, filename)
      }
      case Parsed.Failure (lastParser, index, extra) => {
        println ("Failed to parse file \"%s\".  Last parser is %s.  Index is %d.  Extra is %s".format (filename, lastParser, index, extra))
      }
    }
  }


  def main (args : Array[String]) {
    println ("=" * 80)
    
    import java.io.File
    for (f  f1.getName < f2.getName);
         if (f.getName.endsWith (".naive"))) {
      test (MyParsers.start, f.getPath)
      println ("=" * 80)
    }
  }
}