About Programming / Algorithms / ANSI/POSIX C

File Transfer Client and Server using Vigenere Cipher

[Disclaimer: This code is provided for educational purposes, you are responsible of how you use this code and this code is provided ‘as is’. Meaning that I do not take responsibility of  any harm that this code may or not produce]

The following is an example of a client and server that let you transfer a file from the client to the server by encrypting and then decrypting the packages using Vigenere Cipher.

Test file content example:

Note: This program is designed only to send files that are alphabetic in lower case, without spaces, and  only one line.

abcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyza

Makefile:

As a good policy, always add your name, short description, and any other information that could help a user that doesn’t know as you the content of your code and its behaviour.

Note: In the server, there must be a subdirectory named cli_serv in which ssh and scp can access after loading.



#########################################################################
# Author: Alejandro G. Carlstein Ramos Mejia
# Description: Client/Server File Transfer using Vergene Cipher
#
#
# make <= compile all files
# make build <= compile all files
# make all <= clean and compile all files
# make ssh <= Connect to server and go to folder cli_serv
# make upload <= Upload files on SRC_FILES list to server
# make uploadssh <= Upload files on SRC_FILES list to server and connect to server
# make submit <= Tar files on SRC_FILES list
# make zipsubmit <= Tar files on SRC_FILES list and gzip them
# make clean <= Clean all executable and *.o files
# make debug_server <= Debug server using dbg
# make debug_client <= Debug client using dbg
# make ldebug_server <= Debug for leaks on server
# make ldebug_client <= Debug for leaks on client
##########################################################################

##########################################################################
# Variables
##########################################################################

# PROJECT is the name used when preparing for sumit/
# The tar and/or zip file will be using this name
PROJECT = server_client_vergene

# SRC_FILES are list of files in the project.
# This list is used when uploading files to the server.
# Also, this list is used when tar/zipped for submit
SRC_FILES = \
	cli.c \
	serv.c\
	default.h \
	default.c \
	text.txt\
	Makefile \
	README

# OpenSSH SSH client (remote login program)
SSH = ssh

# secure copy (remote file copy program)
# SCP is used for uploading files to the server in secure mode
SCP = scp

# FOLDER_SERVER is the folder that SSH and SCP will try to access after login
FOLDER_SERVER = server_client_vergene

# SSH_SERVER is the hostname of the server
SSH_SERVER = bingsuns2.cc.binghamton.edu

# SSH_OPTION
# -t opens a pseudo-tty with in the current session.
# This flag is required to execute the commands on SSH_CD_FOLDER
SSH_OPTION = -t

# SSH_CD_FOLDER executes cd
# Then change the prompt to show the number of bash in the server
SSH_CD_FOLDER = 'cd $(FOLDER_SERVER); bash; echo $PS1'

# CC indicates which compiler is going to be used
CC = gcc

# Files required for compiling the server
CODE_SERVER_FILE = serv.c default.c

# Files required for compiling the client
CODE_CLIENT_FILE = cli.c default.c

# Name of the executable file for the server
EXEC_SERVER_FILE = serv

# Name for the executable file for the client
EXEC_CLIENT_FILE = cli

# Flags for the compiler
# -g indicate to provide debuggin information
# -Wall activates the warnings.
# -lm indicate the compiler to add basic mathematics libraries
CFLAGS = -g -Wall -lm

# COMPILE is the combination of the compiler with the flags
COMPILE = $(CC) $(CFLAGS)

# MFLAGS are flags that require to be added at the end
MFLAGS =

# USERNAME is used later when required to do an upload followed with ssh
USERNAME =

# Detect if the computer is SunOS to add flags needed for compiling
UNAME := $(shell uname)
ifeq ($(UNAME), SunOS)
 MFLAGS := -lsocket -lnsl
endif

##########################################################################
# 'make' options
##########################################################################

# Clean all files and compile client and server
all: clean compile_server compile_client

# Just build server and client
build: compile_server compile_client 

# Compile server
compile_server: $(CODE_SERVER_FILE)
	$(CC) $(CFLAGS) -o $(EXEC_SERVER_FILE) $(CODE_SERVER_FILE) $(MFLAGS)

# Compile client
compile_client: $(CODE_CLIENT_FILE)
	$(CC) $(CFLAGS) -o $(EXEC_CLIENT_FILE) $(CODE_CLIENT_FILE) $(MFLAGS)

# Debug server
debug_server:
	gdb $(EXEC_SERVER_FILE) 

# Debug client
debug_client:
	gdb $(EXEC_CLIENT_FILE) 

# Leak debug server
ldebug_server:
	valgrind --leak-check=full --show-reachable=yes -v $(EXEC_SERVER_FILE)

# Leak debug client
ldebug_client:
	valgrind --leak-check=full --show-reachable=yes -v $(EXEC_CLIENT_FILE)

# Upload files and connect to server
uploadssh:
	@echo -n 'Upload and connect to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SCP) $(SRC_FILES) $$user_name@$(SSH_SERVER):./$(FOLDER_SERVER);\
	$(SSH) $(SSH_OPTION) $$user_name@$(SSH_SERVER) $(SSH_CD_FOLDER);\

# Upload files to server
upload:
	@echo -n 'Upload to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SCP) $(SRC_FILES) $$user_name@$(SSH_SERVER):./$(FOLDER_SERVER);\

# Connect to server
ssh:
	@echo -n 'Connect to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SSH) $(SSH_OPTION) $$user_name@$(SSH_SERVER) $(SSH_CD_FOLDER);\

# Makes a archive containing all the project source files for submission.
submit:	$(SRC_FILES)
	tar -cvf $(PROJECT).tar $(SRC_FILES)

# Makes a archive containing all the project source files for submission
# and zip them
zipsubmit:	$(SRC_FILES)
	tar cvfz $(PROJECT).tar.gz $(SRC_FILES)

# Clean files
.PHONY: clean
clean:
	rm -f *~ *.o $(EXEC_SERVER_FILE) $(EXEC_CLIENT_FILE)

Default file is required for both the server and the client. It holds the libraries and definitions shared by both programs.

Default.h file:

/**
 * Author: Alejandro G. Carlstein
 * Description: File Transfer Client/Server
 */

#ifndef ACARLS_DEFAULT_H
#define ACARLS_DEFAULT_H

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <unistd.h>
#include <dirent.h>

/* Required for linux */
#include <string.h>

/* Required for SunOS */
#include <strings.h>

#include <ctype.h>

#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <netdb.h>

#define DEFAULT_PORT 					8414
#define DATA_PACKET_SIZE 			1024
#define NUM_BYTES							8
#define ENCRYPTION_KEY		    'security'
#define CHAR_KEY_A						97
#define CHAR_PLAIN_A					97
#define CHAR_CIPHER_A					65

#define DBG_LV0 0
#define DBG_LV1 0
#define DBG_LV2 0
#define DBG_LV3 0

#define TRUE									1
#define FALSE									0

#define QUIT_TRUE							0
#define QUIT_FALSE						1

#define CODE_FAIL							'0FAIL'
#define CODE_OK								'1OK'

#define CODE_HELLO						'100HELLO'
#define CODE_WELCOME 					'101WELCOME'
#define CODE_REQ_SERVER_NAME 	'102REQ_SERVER_NAME'

#define CODE_MSG 							'200MSG'

#define CODE_DATA							'300DATA'
#define CODE_EOF							'301EOF'
#define CODE_PUT						  '302PUT'
#define CODE_REQUEST_FILENAME	'303REQ_FILENAME'
#define CODE_REQUEST_ENCRYPT  '304REQ_ENCRYPT'
#define CODE_ENCRYPT					'305ENCRYPT'
#define CODE_REQUEST_FILE     '306REQUEST_FILE'

#define CODE_CMD							'400CMD'
#define CODE_LS								'401LS'

#define CODE_ERROR            '500ERROR'
#define CODE_ERROR_LS					'501ERROR_LS'
#define CODE_ERROR_CREAT_FILE '502ERROR_CREAT_FILE'

#define CODE_EXIT							'600EXIT'

#define MSG_ERR_WRONG_PROTOCOL  'Wrong protocol!'
#define MSG_ERROR_CREAT_FILE 		'Couldn't create file'
#define MSG_PORT_NUMBER_ONLY 		'Need port number only! \n%s <Port Number>'
#define MSG_ERR_COULDNT_SOCKET  'Couldn't obtain socket - %d'
#define MSG_ERR_COULDNT_CONNECT 'Couldn't connect!'
#define MSG_ERR_SENDING_DATA 		'Couldn't send data!'
#define MSG_ERR_RECEIVING_DATA	'Couln't recieve data!'
#define MSG_ERR_CONNECTION_FAIL 'Connection failed.'
#define MSG_ERR_NO_DIR_STREAM 	'Could not obtain the directory stream'

void debug(int debugLevel, char *fmt, ...);
void errorDoExit(char *fmt, ...);

#endif

Default.c: 

/**
 * Author: Alejandro G. Carlstein
 * Description: File Transfer Client/Server
 */

#include 'default.h'

void debug(int debugLevel, char *fmt, ...){
	if (debugLevel == 1){
		va_list argp;
		fprintf(stdout, '[DBG] ');
		va_start(argp, fmt);
		vfprintf(stdout, fmt, argp);
		va_end(argp);
		fprintf(stdout, '\n');
	}
}

void errorDoExit(char *fmt, ...){
	va_list argp;
	fprintf(stderr, '[Error] ');
	va_start(argp, fmt);
	vfprintf(stderr, fmt, argp);
	va_end(argp);
	if (errno){
		fprintf(stderr, '=> %s\n', strerror(errno));
	}else{
		fprintf(stderr, '\n');
	}
	exit(1);
}

The following is the code for the server.
serv.c:

/**
 * Assignment: 1
 * Course: CS458
 * Author: Alejandro G. Carlstein
 * Description: FTP Server
 */

#include 'default.h'

/*max. length queue of pending connections may grow. */
#define MAX_BACKLOG							5
#define SETSOCKOPT_VAL  				1

#define MSG_SERVER_NAME 				'Server Name: ACARLSTEIN Server Version 1.0'
#define MSG_WAIT_CLIENT					'Waiting client...\n'
#define MSG_WAIT_CLIENT_ON_PORT	'\nTCPServer Waiting for client on port %d\n'

#define MSG_ERR_NO_SOCKET_OPT		'Couldn't set and/or get socket options'
#define MSG_ERR_UNABLE_BIND    	'Unable to bind'
#define MSG_ERR_UNABLE_LISTEN  	'Unable to Listen'
#define MSG_ERR_CANT_SEND_LIST  'Can't send server list\n'

struct Connection{
	int sock;
	int bytes_recieved;
	int port_number;
	int socket_descriptor;
	char send_data[DATA_PACKET_SIZE];
	char recv_data[DATA_PACKET_SIZE];
  struct sockaddr_in server_addr;
  struct sockaddr_in client_addr;
};

void setUpConnection(struct Connection *new_connection,
										 int port_number);
int menuDriver(struct Connection *new_connection);
void sendData(struct Connection *new_connection,
							const char* data);
int recieveData(struct Connection *new_connection);
void handShake(struct Connection* new_connection);
void sendListDirectoryContents(struct Connection* new_connection);
int receiveFileFromClient(struct Connection* new_connection);
int strdecrypt(const char* str_in,
							 char* str_out);

/**
 * MAIN
 */
int main(int argc, char *argv[]){
	debug(DBG_LV0, 'argc: %d', argc); 	

	short DO_QUIT_PROGRAM;
	int i;
	int port_number;
	socklen_t sin_size = sizeof(struct sockaddr_in);
	struct Connection connection;

	for(i = 0; DBG_LV1 && i < argc; ++i)
		debug(DBG_LV1, 'argv[%d]: %s', i, argv[i]); 		

	if (argc > 2)	errorDoExit(MSG_PORT_NUMBER_ONLY, argv[0]);

	port_number = (argc == 2) ? atoi(argv[1]) : DEFAULT_PORT;

	DO_QUIT_PROGRAM = QUIT_FALSE;
	while(DO_QUIT_PROGRAM){

		fflush(stdout);

		setUpConnection(&connection, port_number);

		printf(MSG_WAIT_CLIENT_ON_PORT, port_number);

		connection.socket_descriptor = accept(connection.sock,
													  						  (struct sockaddr *)&connection.client_addr,
																				  &sin_size);

		if (connection.socket_descriptor  == -1)
			errorDoExit(MSG_ERR_COULDNT_CONNECT);

		handShake(&connection);

 		menuDriver(&connection);

		close(connection.sock); 		

	}

  return 0;
}

/**
 * Menu driver waiting for instructions
 */
int menuDriver(struct Connection *new_connection){

	short DO_QUIT_CONNECTION;
	int bytes_received = 1;

	DO_QUIT_CONNECTION = QUIT_FALSE;
 	while (DO_QUIT_CONNECTION){  

		if(bytes_received == 0){
			DO_QUIT_CONNECTION = QUIT_TRUE;
		}else{

			printf(MSG_WAIT_CLIENT);

			bytes_received = recieveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_LS) == 0){
				sendListDirectoryContents(new_connection);
			}else
			if (strcmp(new_connection->recv_data, CODE_PUT) == 0){
				bytes_received = receiveFileFromClient(new_connection);
			}else{
				close(new_connection->sock);
				fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - PUT\n');
				DO_QUIT_CONNECTION = QUIT_TRUE;
			}
		}
	}
	return 0;
}

/**
 * Set up connection with the client
 */
void setUpConnection(struct Connection *new_connection,
										 int port_number){
	debug(DBG_LV0, 'setUpConnection(port_number: %d)', port_number);

	int opt_val = SETSOCKOPT_VAL;
	new_connection->port_number = port_number;

  if ((new_connection->sock = socket(AF_INET, SOCK_STREAM, 0)) == -1)
		errorDoExit(MSG_ERR_COULDNT_SOCKET, new_connection->sock);

	if (setsockopt(new_connection->sock, SOL_SOCKET, SO_REUSEADDR, &opt_val, sizeof(int)) == -1)
		errorDoExit(MSG_ERR_NO_SOCKET_OPT);

	debug(DBG_LV1, 'Got socket!');

  new_connection->server_addr.sin_family = AF_INET;
 	debug(DBG_LV1,'sin_family');      

  new_connection->server_addr.sin_port = htons(port_number);
	debug(DBG_LV1,'sin_port');

  new_connection->server_addr.sin_addr.s_addr = INADDR_ANY;
	debug(DBG_LV1, 'sin_addr');

  bzero(&(new_connection->server_addr.sin_zero), NUM_BYTES);
	debug(DBG_LV1,'sin_zero');

	// bind a name to a socket
  if (bind(new_connection->sock,
  				(struct sockaddr *)&new_connection->server_addr,
  				sizeof(struct sockaddr)) == -1){
		close(new_connection->sock);
		errorDoExit(MSG_ERR_UNABLE_BIND);
	}

	// Listen for connection on the socket
  if (listen(new_connection->sock, MAX_BACKLOG) == -1){
		close(new_connection->sock);
   	errorDoExit(MSG_ERR_UNABLE_LISTEN);
  }
	debug(DBG_LV1, 'Listening...');	

}

/**
 * Send data to client
 */
void sendData(struct Connection *new_connection,
							const char* data){
	debug(DBG_LV0, 'sendData(data: %s)', data);

 	int data_length;

	bzero(new_connection->send_data, DATA_PACKET_SIZE);
 	strcpy(new_connection->send_data, data);
 	data_length = strlen(new_connection->send_data);

 	debug(DBG_LV1, 'new_connection->send_data: %s',
 	      new_connection->send_data);

	if (send(new_connection->socket_descriptor,
					 new_connection->send_data,
					 data_length, 0) != data_length){
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_SENDING_DATA '\n');
	}
}

/**
 * Receive data from client
 */
int recieveData(struct Connection *new_connection){
	debug(DBG_LV0, 'recieveData()');

	bzero(new_connection->recv_data, DATA_PACKET_SIZE);
	int bytes_recieved = recv(new_connection->socket_descriptor,
														new_connection->recv_data,
														DATA_PACKET_SIZE,
														0);		

	debug(DBG_LV1, 'Check bytes received');

	if(bytes_recieved < 1){

		close(new_connection->sock);

		if(bytes_recieved == 0){
			fprintf(stderr, MSG_ERR_CONNECTION_FAIL '\n');
		}else{
			fprintf(stderr,MSG_ERR_RECEIVING_DATA '\n');
		}

	}else{

		debug(DBG_LV1, 'Received: %s', new_connection->recv_data);

		new_connection->bytes_recieved = bytes_recieved;
  	new_connection->recv_data[bytes_recieved] = '\0';
  }

  return bytes_recieved;
}

/**
 * Hand shake with client to test own protocol
 */
void handShake(struct Connection* new_connection){
	debug(DBG_LV0, 'handShake()');

	printf('Connection from (%s , %d)...\n',
         inet_ntoa(new_connection->client_addr.sin_addr),
         ntohs(new_connection->client_addr.sin_port));

	debug(DBG_LV1,' If client say HELLO, Greed client with WELCOME');
 	recieveData(new_connection);
	if (strcmp(new_connection->recv_data, CODE_HELLO) == 0){
		debug(DBG_LV1, 'Client handshake with server');
		sendData(new_connection, CODE_WELCOME);
	}else{
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - HELLO/WELCOME \n');
	}

	debug(DBG_LV0,'If client ask for server name send server name to client');
 	recieveData(new_connection);
	if (strcmp(new_connection->recv_data, CODE_REQ_SERVER_NAME) == 0){
		debug(DBG_LV1, 'Client asking for server name');
		sendData(new_connection, MSG_SERVER_NAME);
	}else{
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - SERVER NAME\n');
	}
}

/**
 * Send list of directory contents to client
 */
void sendListDirectoryContents(struct Connection* new_connection){
	debug(DBG_LV0, 'void displayLocalListDirectoryContents()');
	int bytes_received;
	struct dirent *dirent_struct_ptr;
	DIR *directory_stream_ptr;

	if ((directory_stream_ptr = opendir('./')) != NULL){

  	while ((dirent_struct_ptr = readdir(directory_stream_ptr))){
			sendData(new_connection, dirent_struct_ptr->d_name);				

			bytes_received = recieveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_OK) != 0){
				fprintf(stderr, MSG_ERR_CANT_SEND_LIST);
			}
   	}
		sendData(new_connection, CODE_EOF);			  		

	}else{
		sendData(new_connection, CODE_ERROR_LS);
		errorDoExit(MSG_ERR_NO_DIR_STREAM);
	}

}

/**
 * Receive encrypted file from client
 */
int receiveFileFromClient(struct Connection* new_connection){
	debug(DBG_LV0, 'void receiveFileFromClient(is_encrypted: %s)');											

	int bytes_received;

	char filename[DATA_PACKET_SIZE];
	char filename_se[DATA_PACKET_SIZE];
	char filename_sd[DATA_PACKET_SIZE];
	char str_unencrypted[DATA_PACKET_SIZE];
	FILE *fp_se, *fp_sd;

	/* Request filename */
	debug(DBG_LV1, 'Request filename from client');
	sendData(new_connection, CODE_REQUEST_FILENAME);

	/* receive filename */
	bytes_received = recieveData(new_connection);
	strcpy(filename, new_connection->recv_data);
	sprintf(filename_se, '%s_se', filename);
	sprintf(filename_sd, '%s_sd', filename);

	debug(DBG_LV1, 'filename: %s', filename);
	debug(DBG_LV1, 'filename_se: %s', filename_se);
	debug(DBG_LV1, 'filename_sd: %s', filename_sd);	

	fp_se = fopen(filename_se, 'w');
	fp_sd = fopen(filename_sd, 'w');
	debug(DBG_LV1, 'Files open');

	if (fp_se == NULL || fp_sd == NULL){
		debug(DBG_LV1, 'Error, closing files');
		fclose(fp_se);
		fclose(fp_sd);
		errorDoExit(MSG_ERROR_CREAT_FILE);
	}else{

		debug(DBG_LV1, 'Download file...');
		/* Send code request file */
		sendData(new_connection, CODE_REQUEST_FILE);				

		bytes_received = recieveData(new_connection);

  	/* while loop until eof */
  	while (strcmp(new_connection->recv_data, CODE_EOF) != 0){

			debug(DBG_LV1, 'Saving: %s', new_connection->recv_data);
	  	/* save encrypted package */
			fprintf(fp_se, '%s', new_connection->recv_data);

			/* Decencrypt package */
			bzero(str_unencrypted, DATA_PACKET_SIZE);
			strdecrypt(new_connection->recv_data, str_unencrypted);
			debug(DBG_LV1, 'Decrypt: %s\n', new_connection->recv_data);

			/* Save unecrypted package */
			debug(DBG_LV1, 'DECRYPT: %s', str_unencrypted);

			fprintf(fp_sd, '%s', str_unencrypted);

			debug(DBG_LV1, 'Sending OK...');
	  	/*send ok */
			sendData(new_connection, CODE_OK);
			bytes_received = recieveData(new_connection);
  	}

	}	

	fclose(fp_se);
	fclose(fp_sd);
	return 0;
}

/**
 * Decrypt string
 */
int strdecrypt(const char* str_in,
							 char* str_out){
	debug(DBG_LV0, 'strdencrypt(str_in: %s)', str_in);

	int i, j;
	int i_cipher, i_key, i_temp;
	char str_key[DATA_PACKET_SIZE];
	strcpy(str_key, ENCRYPTION_KEY);
	char char_temp;
	for (i = 0, j = 0; i < strlen(str_in); ++i, ++j){

		i_cipher = str_in[i] - CHAR_CIPHER_A;
		i_key = str_key[j] - CHAR_KEY_A;
		i_temp = i_cipher - i_key;

		debug(DBG_LV1, 'Ci([%c]%d): %d, Ki([%c]%d): %d, Ci - Ki: %d',
					str_in[i], i, i_cipher, str_key[j], j, i_key, i_temp);

		if (i_temp > -1){
			//COMMON KNOWN DECRYPT ALGORIGHTM
			i_temp = ((i_temp) % 26);
		}else{
			//DECRYPT ALGORITHM FOR UNCOMMON CASES WHERE I_TEMP IS NEGATIVE
			i_temp = ((i_temp + 26) % 26);
		}

		char_temp = i_temp + CHAR_PLAIN_A;
		if (isalpha(char_temp)){
			str_out[i] = char_temp;
		}else{
			str_out[i] = '\0';
		}

		if ( (j + 1) >= strlen(str_key)) j = -1;
	}

	return 0;
}

The following is the code for the client.

cli.c

/**
 * Assignment: 1
 * Course: CS458
 * Author: Alejandro G. Carlstein
 * Description: Transfer Encrypted File Client
 */

#include 'default.h'

#define DEFAULT_HOST 									'localhost'
#define EXIT_PROGRAM 									0
#define DONT_EXIT_PROGRAM 						1

#define CMD_QUIT											'quit'
#define CMD_HELP											'help'
#define CMD_LS												'ls'
#define CMD_LLS												'lls'
#define CMD_LPWD											'lpwd'
#define CMD_PUT												'put'

#define MSG_DISPLAY_MENU 							'User help:\n'\
																			'help - Display help option\n'\
																		  'lls  - Display local directory list contents\n'\
                    				          'lpwd - Display local current directory\n'\
                    				          'put  - Transfer local file to server\n'\
                    				          '  put <file to transfer>\n'\
                    				          'quit - Quit program\n'

#define MSG_ERROR_UNKNOWN_COMMAND			'[X] Command not recognized: %s\n'
#define MSG_ERROR_GETTING_HOSTNAME 		'Couln't get hostname!'
#define MSG_ERROR_SERVER_DISCONNECTED 'Server disconnected...\n'

enum TOKENS{
	TOKEN_COMMAND,
	TOKEN_FILENAME,
	MAX_TOKENS
};

struct Connection{
	int sock;
	int bytes_received;
	int port_number;
	char send_data[DATA_PACKET_SIZE];
	char recv_data[DATA_PACKET_SIZE];
	struct hostent *host;
  struct sockaddr_in server_addr;
};

void getConnection(struct Connection *new_connection,
									 char *hostname,
									 int port_number);
void menuDriver(struct Connection *new_connection);
int receiveData(struct Connection *new_connection);
int sendData(struct Connection* new_connection, const char* data);
void handShake(struct Connection* new_connection);
void promptUser(char* tokens[]);
void displayHelp(void);
void displayLocalListDirectoryContents(void);
void printNameCurrentDirectory(void);
void receiveListDirectoryContents(struct Connection *new_connection);
void putFileOnServer(struct Connection *new_connection,
										 const char* filename);
int strencrypt(const char* str_in,
               char* str_out);
/**
 * MAIN
 */
int main(int argc, char* argv[]){
	debug(DBG_LV0, 'argc: %d', argc); 	

	int i;
	int port_number = (argc >= 3 ) ? atoi(argv[2]) : DEFAULT_PORT;
	char* host_name = (argc >= 2) ? argv[1] : DEFAULT_HOST;

	struct Connection connection;

	for(i = 0; i < argc; ++i)
		debug(DBG_LV0, 'argv[%d]: %s', i, argv[i]); 		

	if (argc > 3)
		errorDoExit(MSG_PORT_NUMBER_ONLY, argv[0]);

	debug(DBG_LV1, 'host: %s', host_name);

	getConnection(&connection, host_name, port_number);

	handShake(&connection);

	menuDriver(&connection);

	return 0;

}

/**
 * Driver menu
 */
void menuDriver(struct Connection *new_connection){
	debug(DBG_LV0, 'menuDriver()');

	short doExit = DONT_EXIT_PROGRAM;
	int i;
	char* tokens[MAX_TOKENS] = {NULL, NULL};
	char command[DATA_PACKET_SIZE];
	char filename[DATA_PACKET_SIZE];

  while(doExit){

		promptUser(tokens);				

		for (i = 0; DBG_LV1 && i < MAX_TOKENS; ++i)
			debug(DBG_LV1, 'TOKEN[%d]: %s', i, tokens[i]);

		/* Must copy string to work on SunOS */
		if (tokens[TOKEN_COMMAND] != NULL){
			strcpy(command, tokens[TOKEN_COMMAND]);
   		debug(DBG_LV1, '[Command: %s]', command);
		}

		if (tokens[TOKEN_FILENAME] != NULL){
    	strcpy(filename, tokens[TOKEN_FILENAME]);
	    debug(DBG_LV1, '[Filename: %s]', filename);
    }

		/* MENU */

		if (strcmp(command, CMD_QUIT) == 0){
			debug(DBG_LV1, 'COMMAND> %s: ', CMD_QUIT);
			close(new_connection->sock);
			printf('Bye Bye\n');
			doExit = EXIT_PROGRAM;

		}else
		if (strcmp(command, 'help') == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_HELP);
			displayHelp();

		}else
		if (strcmp(command, CMD_LLS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LLS);
			displayLocalListDirectoryContents();

		}else
		if (strcmp(command, CMD_LLS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LLS);
			displayLocalListDirectoryContents();

		}else
		if (strcmp(command, CMD_LS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LS);
			receiveListDirectoryContents(new_connection);

		}else
		if (strcmp(command, CMD_LPWD) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LPWD);
			printNameCurrentDirectory();

		}else
		if (strcmp(command, CMD_PUT) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_PUT);
			putFileOnServer(new_connection, filename);

		}else{
			printf(MSG_ERROR_UNKNOWN_COMMAND, command);
		}

	}

}

/**
 * Obtain connection with server
 */
void getConnection(struct Connection *new_connection,
									 char *hostname,
									 int port_number){
	debug(DBG_LV0, 'getConnection(hostname: %s, port_number: %d)', hostname, port_number);

	if ((new_connection->host = gethostbyname(hostname)) == NULL)
		errorDoExit(MSG_ERROR_GETTING_HOSTNAME);

	new_connection->port_number = port_number;	

	if ((new_connection->sock = socket(AF_INET, SOCK_STREAM, 0)) == -1)
		errorDoExit(MSG_ERR_COULDNT_SOCKET, new_connection->sock);

	debug(DBG_LV1, 'Got socket!');

  new_connection->server_addr.sin_family = AF_INET;
	debug(DBG_LV1,'sin_family');

  new_connection->server_addr.sin_port = htons(port_number);
	debug(DBG_LV1,'sin_port');

  new_connection->server_addr.sin_addr = *((struct in_addr *)new_connection->host->h_addr);
	debug(DBG_LV1, 'sin_addr');

	// bzero() is used only for setting the values to zero
	bzero(&(new_connection->server_addr.sin_zero), NUM_BYTES);
	debug(DBG_LV1,'sin_zero');

  if (connect(new_connection->sock,
  					  (struct sockaddr *)&new_connection->server_addr,
  					  sizeof(struct sockaddr)) == -1)
		errorDoExit(MSG_ERR_COULDNT_CONNECT);

	debug(DBG_LV1, 'Got connection!');
}

/**
 * Receive data
 * @Return: Number of bytes received
 */
int receiveData(struct Connection *new_connection){
	debug(DBG_LV0, 'receiveData()');

	bzero(new_connection->recv_data, DATA_PACKET_SIZE);
	int bytes_received = recv(new_connection->sock,
														new_connection->recv_data,
														DATA_PACKET_SIZE,
														0);		

	if(bytes_received < 1){
		close(new_connection->sock);
		if(bytes_received == 0){
			close(new_connection->sock);
			printf(MSG_ERROR_SERVER_DISCONNECTED);
			errorDoExit(MSG_ERR_CONNECTION_FAIL);		

		}else{
			errorDoExit(MSG_ERR_RECEIVING_DATA);
		}
	}

	debug(DBG_LV1, 'Received (%d): %s',
				strlen(new_connection->recv_data), new_connection->recv_data);	

	new_connection->bytes_received = bytes_received;
  new_connection->recv_data[bytes_received] = '\0'; 

  return bytes_received;
}

/**
 * Send data
 * @Return: Number of bytes sended
 */
int sendData(struct Connection* new_connection,
						const char* data){
	debug(DBG_LV0, 'sendData(%s)', data);
	int data_length;

	bzero(new_connection->send_data, DATA_PACKET_SIZE);
	strcpy(new_connection->send_data, data);
	data_length = strlen(new_connection->send_data);

	if (send(new_connection->sock, new_connection->send_data,
					 data_length, 0) != data_length){
		close(new_connection->sock);
		errorDoExit(MSG_ERR_SENDING_DATA);
	}

	return data_length;
}

/**
 * Hand shake with the server to verify own protocol
 */
void handShake(struct Connection* new_connection){
	debug(DBG_LV0, 'handShake()');

	debug(DBG_LV1, 'Sending HELLO message...');
	sendData(new_connection, CODE_HELLO);

	debug(DBG_LV1, 'Getting WELCOME message...');
	receiveData(new_connection);  		

	if (strcmp(new_connection->recv_data, CODE_WELCOME) > -1){
		debug(DBG_LV1, 'Got WELCOME!');

		debug(DBG_LV1, 'Request server name');
		sendData(new_connection, CODE_REQ_SERVER_NAME);

		receiveData(new_connection);
		printf('Server Name: %s\n', new_connection->recv_data);
	}else{
		errorDoExit(MSG_ERR_WRONG_PROTOCOL);
	}
}

/**
 * Prompt user for input
 */
void promptUser(char* tokens[]){
	char str_input[DATA_PACKET_SIZE];
	char *p;
	int i;

	printf('\nftp> ');
	fgets(str_input, DATA_PACKET_SIZE, stdin);		

	p = strtok(str_input, ' \n');
  for (i = 0; p != NULL; (p = strtok(NULL, ' \n')), i++)
		tokens[i] = p;
}

/**
 * Display help message
 */
void displayHelp(void){
	debug(DBG_LV0, 'displayHelp()');
	printf(MSG_DISPLAY_MENU);
}

/**
 * Display local list directory contents
 */
void displayLocalListDirectoryContents(void){
	debug(DBG_LV0, 'void displayLocalListDirectoryContents()');

	struct dirent *dirent_struct_ptr;
	DIR *directory_stream_ptr;

	if ((directory_stream_ptr = opendir('./')) != NULL){
		printNameCurrentDirectory();

  	while ((dirent_struct_ptr = readdir(directory_stream_ptr))){
	  	printf(' %s\n',dirent_struct_ptr->d_name);
   	}
	}else{
		errorDoExit(MSG_ERR_NO_DIR_STREAM);
	}

}

/**
 * Print the name of the current directory
 */
void printNameCurrentDirectory(void){
	debug(DBG_LV0, 'void printNameCurrentDirectory()');

	long size;
	char *buf;
	char *ptr;
	size = pathconf('.', _PC_PATH_MAX);
	if ((buf = (char *)malloc((size_t)size)) != NULL){
		ptr = getcwd(buf, (size_t)size);
	}else{
		errorDoExit('Could not obtain the current directory');
	}
	printf('Current Directory: %s\n', ptr);
}

/**
 * Receive the list of directory contents from the server
 */
void receiveListDirectoryContents(struct Connection *new_connection){
	debug(DBG_LV0, 'receiveListDirectoryContents()');

	sendData(new_connection, CODE_LS);

	receiveData(new_connection);
	while (strcmp(new_connection->recv_data, CODE_EOF) != 0){

		if (strcmp(new_connection->recv_data, CODE_ERROR_LS) == 0){
			fprintf(stderr, 'Couldn't read list directory contents!\n');
			break;
		}else{
			printf('%s\n', new_connection->recv_data);
			sendData(new_connection, CODE_OK);
		}
		receiveData(new_connection);
	}

}

/**
 * Put an encrypted file on the server
 */
void putFileOnServer(struct Connection *new_connection,
										 const char* filename){
	debug(DBG_LV0, 'void putFileOnServer(filename: %s)', filename);

	char str_filename[DATA_PACKET_SIZE];
	char filename_ce[DATA_PACKET_SIZE];
	char str_in_file[DATA_PACKET_SIZE];
	char str_in_file_encrypt[DATA_PACKET_SIZE];
	FILE *fp, *fp_ce;

	strcpy(str_filename, filename);

	debug(DBG_LV1, 'str_filename: %s', str_filename);

	sprintf(filename_ce, '%s_ce', str_filename);

	debug(DBG_LV1, 'filename_ce: %s', filename_ce);

	debug(DBG_LV1, 'OPEN FILE TO READ');
	fp = fopen(str_filename, 'r');

	debug(DBG_LV1, 'OPEN FILE TO WRITE');
	fp_ce = fopen(filename_ce, 'w');

	if (fp == NULL || fp_ce == NULL){
		fclose(fp_ce);
		fclose(fp);
		errorDoExit('Couldn't open file');
	}else{

		/* Send PUT code to server */
		sendData(new_connection, CODE_PUT);

		debug(DBG_LV0, 'Waiting for CODE_REQUEST_FILENAME');
		/* Receive filename request form server */
		receiveData(new_connection);
		if (strcmp(new_connection->recv_data, CODE_REQUEST_FILENAME) == 0){

			debug(DBG_LV0, 'Send filename');
			/* Send filename to server */
			sendData(new_connection, str_filename);

			/* Receive request to send file */
			receiveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_REQUEST_FILE) == 0){
				printf('Sending file: %s.\n', filename);
					/* Encrypt file */
				while(fgets(str_in_file, DATA_PACKET_SIZE, fp) != NULL){
					debug(DBG_LV2, 'Reading (Len: %d): %s', strlen(str_in_file), str_in_file);						

					/* encrypt package */
					strencrypt(str_in_file, str_in_file_encrypt);

					/* Save it in <filename>_ce */
					fprintf(fp_ce, '%s', str_in_file_encrypt);					

					/* send packages */
					sendData(new_connection, str_in_file_encrypt);

					/* Waiting for ok */
					receiveData(new_connection);
					if (strcmp(new_connection->recv_data, CODE_OK) == 0){
						printf('OK');
					}else{
						errorDoExit('Wrong protocol - Waiting OK');
					}	

				}
				sendData(new_connection, CODE_EOF);			

			}else{
				errorDoExit('Wrong protocol - Waiting request for file ');
			}

		}else{
			errorDoExit('Wrong protocol - Waiting for request of filename');
		}

	}

	fclose(fp);
	fclose(fp_ce);

}

/**
 * Encrypt the string using key
 * @Return: Number of bytes encrypted
 */
int strencrypt(const char* str_in,
               char* str_out){
	debug(DBG_LV0, 'strencrypt(str_in: %s)', str_in);

	int i, j;
	int i_plain, i_key;

	char str_key[DATA_PACKET_SIZE];

	strcpy(str_key, ENCRYPTION_KEY);

	for (i = 0, j = 0; i < strlen(str_in) - 1; ++i, ++j){

		i_plain = (unsigned int)str_in[i] - CHAR_PLAIN_A;
		i_key = (unsigned int)str_key[j] - CHAR_KEY_A;

		str_out[i] = (char)((i_plain + i_key) % 26 + CHAR_CIPHER_A);

		debug(DBG_LV1, '(str_out: %d) [%c:%d] = (str_in:%d)[%c:%d], (key:%d)[%c:%d]',
					i, str_out[i], (int)str_out[i],
					i, str_in[i], (int) str_in[i],
					j, str_key[j], (int)str_key[j]);

		if ( (j + 1) >= strlen(str_key)) j = -1;
	}

	return strlen(str_in);
}

When I wrote the code, I was following certain guidelines. As you may think the code could be written better. I agree.

In case you have any questions about the code please post them. I will try to answer you as soon as possible.

Share
Leave a comment
About Programming

Introduction to Concepts of Programming Languages

The follows is an introduction to the concepts of Programming Languages. Some of these concepts are the style of language, the identification of typical error when programming, etc.Lets begin by identifying different styles of programming languages.

Programming languages normally are divided in two categories:

The first category are languages that behave in a declarative way which means we tell the  computer what it is going to do.

Declarative language example: In Prolog, we provide a group of facts and rules, its up to the programming language to figure out the answer:

is_mother_of(maria, pedro). /* Maria is_mother_of Pedro */
is_mother_of(maria, lucia)./* Maria is_mother_of Lucia */

is_father_of(diego, pedro). /* Diego is_father_of Pedro */
is_father_of(manuel, lucia). /* Manuel is_father_of Lucia */

/* Person is_parent_of Child if Person is_mother_of Child */
is_parent_of(Person, Child):- is_mother_of(Person, Child).
is_parent_of(Person, Child):- is_father_of(Person, Child).

In this case, we have that a mother, Maria, who is mother of two children, Pedro and Lucia; however, both children have different fathers. Diego is father of Pedro while Manuel is father of Lucia.

Prolog is going to search for the answer for us base on there facts and rules. If we wish for more answers, it will search for the next one. We can keep asking Prolog to keep searching until there are no more answers to be found.

/* Prolog give us an answer */
?- is_parent_of(Maria, Child).
Maria = maria,
Child = pedro.


/* After Prolog give us an answer, we can ask Prolog to search for another answer using ';' */
?- is_parent_of(Maria, Child).
Maria = maria,
Child = pedro ;
Maria = maria,
Child = lucia. 


In the declarative languages, there exist subcategories of programming  languages such as functional languages, dataflow languages, logic  languages (also known as constraint-based languages), and template based languages.


Functional languages examples: Haskell, Lisp (Scheme), MI.


This languages are based on the use of recursive definitions of functions.


Dataflow languages examples: Val, Id.


These languages are defined as tokens (known as nodes) that are used for the flow of information. This kind of language let the user to work on  an inherently parallel model.


Logic (constraint-based) languages examples: Prolog, spreadsheets (such as Excel).


This kind of languages are designed so the programmer provide relationships and rules in such a way that the computer try to find the values that will satisfy them.


Template based languages example: XSLT.


The second category are imperative languages in which we tell the computer how to find the answer.


Imperative language example: In C, we must tell the language how to solve the problem.


/* This code tell the computer how to do the power of a number */
int PowerI(int pow, int number){
    int accumulator, counter;
    for (accumulator = 1, counter = 0; counter < pow; ++counter){
        accumulator = accumulator * number;
    }
    return accumulator
}


In the imperative languages, there exist subcategories of programming  languages such as scripting languages, object oriented languages, and Von Neumann languages which are based on statements (in honor to the creator of this language  John Von Neumman – http://en.wikipedia.org/wiki/John_von_Neumann) .


Scripting languages examples: Bash, PHP, ASP, Python, Perl, Ruby.


This kind of languages let the programmer to create components and then combine them. The programmer can create a program and run it in real-time without compiling it, since each instruction is interpreted in real-time, letting the programmer to be able to change the program and witness the results instantaneously. However, there is a trade in speed.


Object Oriented languages examples: Java, C++, Small Talk, Eiffel.


This kind of languages work on the concepts of classes that are the blueprint to create objects. Later, the idea is to make these objects to interact between them.


Von Neumann languages examples: Fortran, Ada, C.


These languages are sequential in their process.
Share
Leave a comment
About Programming / Prolog

Prolog using Examples – Part 5

The follow is a continuation of the previous posting “Prolog using Examples – Part 4”

Example 1: Check the prefix of a list.

/* Base case */
/* When the list of prefix checked is empty means that we stop checking */
prefix([],_).

/* Recursive case */
/* Both head of the list must be the same */
prefix([Head|Tail_A], [Head|Tail_B]):-
    prefix(Tail_A, Tail_B).

?- prefix([1,b], [1,b,c,4]).
true.

?- prefix([1,b], [1,d,c,4]).
false.


/* prefix will search for each prefix everytime OR ';' is used */
?- prefix(Lst, [1,2,3,4]).
Lst = [] ;
Lst = [1] ;
Lst = [1, 2] ;
Lst = [1, 2, 3] ;
Lst = [1, 2, 3, 4] ;
false.

/* Generate a list where list [1,2,3,4] is the prefix and the tail is a dynamic variable */
?- prefix([1,2,3,4],Lst).
Lst = [1, 2, 3, 4|_G3713]. 

Example 2: Check the suffix of a list.

/* Base case */
/* When both list are the same, we found the suffix */
suffix(Lst_tail, Lst_tail).

/* Recursive case */
/* We want to check always the tail of the list, so the base case can check if they are the same */
suffix([_|Tail], Lst) :-
    suffix(Tail, Lst).

?- suffix([a,2,c,4],[c,4]).
true.

?- suffix([a,2,c,d],[c,4]).
false.

/* Obtain the next tail everytime OR ';' is used */
?- suffix([1,2,3,4], Lst).
Lst = [1, 2, 3, 4] ;
Lst = [2, 3, 4] ;
Lst = [3, 4] ;
Lst = [4] ;
Lst = [].

/* Be careful, in this kind of cases prolog keep generating dynamic variables in from of the list */
?- suffix(Lst, [1,2,3,4]).
Lst = [1, 2, 3, 4] ;
Lst = [_G3704, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, _G3719, 1, 2, 3|...] ;
... /* Keep generating dynamic variables */

 

Example 3: In this example, we are introducing append. append is the unification of two lists, List_A, List_B, into one list that we are going to call list AB, List_AB.

The code of append is the follow:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

First append will move 1, 2,  and 3 atoms from List_A to List_AB using recursion:

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

append([1,2,3], [4,5,6], []) → append([2,3], [4,5,6], [1])  → append([3], [4,5,6], [1,2])  → append([], [4,5,6], [1,2,3])

When List_A is empty, then it will append List_B to List_AB as a tail of List_AB using the base case:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).


append([], [4,5,6], [1,2,3]) → append([], [], [1,2,3,4,5,6])  → List_AB = [1,2,3,4,5,6]

Example 4: Even do append seems to create a list by appending List_A with List_B, append can behave in a different ways depending of how it is used:

Let see the code for append:

append([], Lst, Lst). /* ← Base case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-  /* ← Recursive case */
    append(Tail_A, List_B, Tail_AB).

 

Lets say we do  append(List_A, [5,6], [1,2,3,4,5,6]). What would be the result?

As you can see List_AB have 1,2,3,4,5, and 6 while List_B have 5 and 6, Prolog will unify List_A with 1,2,3, and 4.

?- append(List_A, [5,6], [1,2,3,4,5,6]).
List_A = [1, 2, 3, 4] .

Share
Leave a comment
About Programming / Algorithms / Prolog

Prolog using examples – Part 4

In this part of this practical tutorial, we are going to do some coding involving facts, rules, recursion, and lists.

Example 1: Obtain the head of the list, obtain the tail of the list.

/* Get the head of the list */
get_head(Head, [Head|_]).

/* Get the tail of the list */
get_tail(Tail, [_|Tail]).

?- get_head(Head_is, [a,b,c,d]).
Head_is = a.

?- get_tail(Tail_is, [a,b,c,d]).
Tail_is = [b, c, d].

Example 2: Find out if an element is a member of a list.

/* Base case - We find the element inside the list */
/* The element is found if the head of the list can be unified with the element we are searching */
member(Element, [Element|_]).

/* Recursive function that call member with the tail without taking care of the head of the list */
/* The idea is that the base case will be called and check if the element is found */
member(Element, [_|Tail]) :-
    member(Element, Tail).    

?- member(a, [a,1,3,b,c]).
true .

/* Using OR ';', we ask Prolog to search for another element in the list */
?- member(a, [a,1,a,b,c]).
true ;
true ;
false.

/* Element is not found in the list */
?- member(a, [c,1,3,b,c]).
false.

Example 3: Find an specific element member inside a list in a determined position.

/* Base case */
/* The element was found in the list was found, set Position to 1 to stop recursion */
get_member_at(1, [Head|_], Head).

/* Recursive case */
/* Go thought the list until position is less than 1 indicating that member was found */
get_member_at(Position, [_|Tail], Element):-
    Position > 1,
    Temp_Position is Position - 1,
    get_member_at(Temp_Position, Tail,  Element).

/* Get the member at position 3 of the list */
?- get_member_at(3, [1,3,5,7], Lst).
Lst = 5. 

/* This fails when trying to get an element out or bounds of the list */
?- get_member_at(5, [1,3,5,7], Lst).
false. 

/* BE CAREFUL, Sometimes prolog can behave weird base on how you use your functors eg.*/

/* The follow is when prolog create dynamic variables because doesn't now the limit of the list */
?- get_member_at(5, Lst, Lst).
Lst = [_G455, _G458, _G461, _G464, **|_G468].

/* In this case, not only produce dynamic variables to be instanciated, but also add
the list [1,a,b] as the fifth head element of the list */
?- get_member_at(5, Lst, [1,a,b]).
Lst = [_G473, _G476, _G479, _G482, [1, a, b]|_G486] ;

Example 4: Lets obtain the numbers of elements that belong to a simple list.

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

In the recursive case, Prolog will call number_of_elements passing the tail of the list until the list is empty. Then, for every time number_of_elements was call it would return the counter + 1 to the previous call. At the end, we will obtain the total number of elements in the list.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 6.

/* In this case the sublist [1,2,3] inside the list is considerate an element as a whole */
?- number_of_elements([a,b,c,[1,2,3]], Counted).
Counted = 4.

?- number_of_elements([[a,b,c,1,2,3]], Counted).
Counted = 1.

If inside the code we would had the unification symbol instead of the word ‘is’, we would have a different result:

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 0+1+1+1+1+1+1.

Example 5: Lets sort a list of elements

/* Base case - Empty list */
sort_list([]).

/* Base case - [_] indicate we don't case about the element, there is only one, the list is sorted */
sort_list([_]).

/* Recursion case */
sort_list([First_element, Second_element|Tail]):-
    First_element =< Second_element,
    sorted([Second_element|Tail]).

?- is_list_sorted([1,2,3,4]).
true .

?- is_list_sorted([1,2,3,4]).
true ;
false.

?- is_list_sorted([1,3,3,4]).
true.

?- is_list_sorted([1,3,5,4]).
false.

This topic will continue in the next posting.

Share
Leave a comment
About Programming / Prolog

Prolog using Examples – Part 3

Prolog have a powerful way to work data by the use of lists. A list is normally a group of elements in each elements would have to pointers, one to the value and another to the next element or rest of the of the list. Just to clarify, we don’t see these pointers.

A list is represented in this way: T = [1, 2, 3, 4, 5] in which T is unified with this list and each number is an element of the list.

You can have also a list inside the list: T = [1, [a, b], 3, 4, 5].

The follows are some examples of how to work with list in Prolog:

Example 1: Lets have two variables, Head and Tail, we want the first element of the list to be unified with the Head variable and the rest of the list to be unified with the tail.

?- [Head|Tail] = [1,2,3,4,5].
H = 1,
T = [2, 3, 4, 5].

Example 2: Let say we wish to obtain the first two elements of the list, First_element and Second_element, and the rest of the list to the variable Tail.

?- [First_element, Second_element|Tail] = [1,2,3,4,5].
First_element = 1,
Second_element = 2,
Tail = [3, 4, 5].

If there are just two elements in the list, the Tail will be pointing to an empty list. An empty list is represented by []

?- [First_element, Second_element|Tail] = [1,2].
First_element = 1,
Second_element = 2,
Tail = [].

A list with less elements that needed, Prolog will indicate us cannot be done.

?- [First_element, Second_element|Tail] = [1].
False


/* Here [A] = [1] means that A is unified with 1, while B is unified with 2,3,4,5 */
?- [[A]|B] = [[1],2,3,4,5].
A = 1,
B = [2, 3, 4, 5].

/* [A|B] = [1,2], C = [3,4,5] → A = 1, B = [2], C = [3,4,5] */
?- [[A|B]|C] = [[1,2],3,4,5].
A = 1,
B = [2],
C = [3, 4, 5].

?- [[A|B]|C] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = [4, 5, 6].

?- [[A|B]|[C|D]] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = 4,
D = [5, 6].


There are cases in which we can use the feature that Prolog provide of unification.


/* This case, we have the same Head. Notice we have two 3's,
one inside the sublist and one of the list */
?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],3,6,7].
Head = 3,
Tail_A = [4, 5],
Tail_B = [6, 7].


The following case would fails because the first list [Head|Tail_A] would unify with [3, 4, 5] and the second [Head|Tail_B] list would unify with [2,6,7], since the atom 3 is not the same as the atom 2 then it false.


?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],2,6,7].
false.


The follow is the same example but using different atoms:


?- [[A|B]|[A|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[A|B]|[A|D]] = [[a,b,c],d,e,f].
false.

?- [[A|B]|[_|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[_|B]|[_|D]] = [[a,b,c],a,e,f].
B = [b, c],
D = [e, f].

?- [[A|T]|[B|T]] = [[a,b,c],d,b,c].
A = a,
T = [b, c],
B = d.


This proves that Prolog consider  numbers as atoms (constants) in the same way as lower case characters/names and strings such as ‘abc’.


Using an underscore inside the brackets indicate that we don’t care about that element or elements:


?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|_] = [1,2,3,4,5].
True


In following posting, we will see how to work with lists using facts, rules, and recursion.
Share
Leave a comment