Discrete Maths, Lecture#1

I'm following a course on discrete mathematics available here. This course was taught at arsdigita university by Shai Simonson who is a professor in computer science department at stonehill college.

I thought a little bit through and decided, to best learn from the available video lectures I should use them like the classroom lecture and take notes. I'm going to write blog post with every lecture I watch and post my notes also.

Lecture#1, Introduction

In this lecture, Shai introduces the course as being a course on all the various techniques of "counting". He gives examples of some counting problems such as in how many ways can we chose two students from a class of n students, how many pins are there in a n-lane bowling alley etc. In discrete maths, it is very important to do proofs, so the lecture starts with discussing the basic proof techniques, proof by contradiction and proof by induction. He gives examples for both the techniques. Next part of the lecture introduces basic logic and boolean algebra.

Here are the notes that I took...

JASI v1 is done

JASI - Just Another Scheme Interpreter

code is here.
other posts related to jasi are here.

I'm done writing java implementation of the scheme interpreter that started just to better my understanding of interpreters in general and to learn what it takes to write one.

This implementation of mine doesn't solve any practical purpose(as of now atleast) and not an optimized one, I gave more importance to modularity and easy readability of the code.

It complies to a subset of R4RS and passes a subset of R4RS tests written by Aubrey Jaffrey, that subset is available with the code in the file tests.scm in top level directory.

Code Organization:
It consists of 4 main packages..

1. jasi.parser
This package contains the classes responsible reading the scheme expressions and provide the functionality of "read". Tokenizer.java does the job of lexical analysis and Reader.java gets tokens from it, reads S-expressions.

2. jasi.datatypes
The classes here represent various scheme datatypes.

3. jasi.symantics
This is the engine of the interpreter. Scheme.java has the "eval" to evaluate s-exps and this is where the language behavior is realized. Environment.java contains the code for maintaining environment and also initial global enironment that becomes available to the user in the interactive mode. If one wants to add another primitive procedure(that can't be implemented in scheme using existing primitives), then he needs to add binding for same in the global environment in Environment.initGlobalEnv() method.

4. jasi.symantics.procedure
CompoundProcedure.java contains the behavior of how user defined procedures are evaluated. PrimitiveProcedure.java contains implementation of (almost)all the primitive procedures.

I've tried to implement only the essential functionality in java, other primitives are written in scheme itself in the file src/main/resources/preloadedscm.scm that is loaded at interpreter startup. If one needs to add another primitive that can be written using the existing primitives, this is the place.

For more info, Please read the "readme" included in the code.

scheme parser = "read"

This is another article for my ongoing learnings with writing a scheme interpreter(hosted here). As I described in my previous post that I started with writing a formal EBNF grammar and a recursive descent parser for it.
When I came to implementing "read" function of scheme, then I realised that it essentially is the parser of scheme and list data structure is AST. Moreover when I write the formal grammar then the syntactical rules of the language are fixed at the time of parsing itself and its very difficult now to provide macros. Instead the parser or the "read" should just read *any* valid s-expression and "eval" only should derive any meaning from it.
So I've now changed my implementation and written a "read" that reads any valid s-expression and "eval" provides meaning to it.

introducing jasi and my first parsing strategy

JASI - Just Another Scheme Interpreter.
I'm doing an experiment of writing a scheme interpreter(hosted here, code discussed in this post is available only upto revision#10).
I've read sometimes about basics of compilers, grammars, ast etc and followed that path to start with. So I started with creating a EBNF grammar(not strictly correct) for a subset of scheme. Then a parser. Basically there are two kind of parsers, Bottom-up(e.g. shift-reduce) and Top-down(e.g. recursive descent). Since this is an experiment, So I wanted to write the parser by hand. Its easy to write a recursive descent parser(algo is simple, each non-terminal symbol has a method to create its part of ast, we start with calling that method of the start non-terminal of the grammar and that in turn recursively calls same method for other non-terminals) by hand, So I tried to write the grammar in a way so that its easy to write a top-down recursive descent parser for it.I removed left recursion, tried to left factorize it so that starter symbol of any non-terminal for each production rule is distinct(from all other production rules for that non-terminal) and single look-ahead is enough to parse. Here is that grammar I wrote to start with...

expr :=
|CHAR    ;charExpr
|STRING    ;stringExpr
|NUMBER    ;numberExpr
|VARIABLE    ; variableExpr
|LPAREN DEFINE VARIABLE expr RPAREN    ;definitionExpr
|LPAREN IF expr expr expr? RPAREN    ;ifExpr
|LPAREN LAMBDA LPAREN variable* RPAREN expr+ RPAREN ;lambdaExpr
 |LPAREN variable expr* RPAREN    ;applicationExpr

CHAR := #\any-non-white-space-char
NUMBER := DIGIT(DIGIT)*
DIGIT := 0|1|2|3|4|5|6|7|8|9
STRING := "any-characters"
LPAREN := '('
RPAREN := )
VARIABLE := [^#0-9()] any-non-white-space-char 

Notice that, I gave labels to each production rule and each label is mapped to a AST in the code. So here is the (classes of)tree structure that I created for ast...

AST
 CharAST
 StringAST
 NumberAST
 VariableAST
 DefinitionAST
 IfAST
 LambdaAST
 ApplicationAST

I wrote a class called Tokenizer to make tokens from stream of characters. Its implemented in terms of a finite state machine. And wrote another Parser class(a recursive descent top down parser) that gets tokens from Tokenizer and builds the AST. The most important method of Parser is here and the beauty is its simplicity(it derives straightforward from the grammar and indeed this is the reason parsers can be generated. :)

public AST parseExpr() {
   Token currentToken = Tokenizer.getNextToken();
   switch(currentToken.getType()) {
       case Constants.TOKEN_TYPE_CHAR:
           return parseCharExpr(currentToken);
       case Constants.TOKEN_TYPE_NUMBER:
           return parseNumberExpr(currentToken);
       case Constants.TOKEN_TYPE_STRING:
           return parseStringExpr(currentToken);
       case Constants.TOKEN_TYPE_VARIABLE:
           return parseVariableExpr(currentToken);
       case Constants.TOKEN_TYPE_LPAREN:
           currentToken = Tokenizer.getNextToken();
           switch(currentToken.getType()) {
               case Constants.TOKEN_TYPE_DEFINE:
                   return parseDefinitionExpr(currentToken);
               case Constants.TOKEN_TYPE_IF:
                   return parseIfExpr(currentToken);
               case Constants.TOKEN_TYPE_LAMBDA:
                   return parseLambdaExpr(currentToken);
               case Constants.TOKEN_TYPE_VARIABLE:
                   return parseApplicationExpr(currentToken);
               default:
                   throw new RuntimeException("Could not" +
                   " parse:" + currentToken.getType() +
                   ":" + currentToken.getSpelling());
           }
       default:
           throw new RuntimeException("Could not " +
           "parse at:" + currentToken.getType() +
                   ":" + currentToken.getSpelling());
   }
}

hibernate code generation

Now a days, I'm working on a server side backend service that exposes an API using a REST interface. To get to the data model, we first created a business domain model which contained business entities, value objects and some enumerations. From this domain model we created a ER diagram and from there a db data model. Next comes the ORM layer(using hibernate) and we figured out that there were two ways to go...

1. Write hibernate hbm files and generate code and db-scripts from them.


2. Create db-scripts from the data-model and reverse engineer this schema to generate hibernate classes and hbm files

At the moment we decided that we want to keep a close grip on what gets created inside db, so we went ahead with the second approach. After some use it looks like, we're taking alot of pain in work-arounds to not to touch generated java code(so that we can change data model anytime and regenerate the code). Let us see if this approach works out fine or if at some point we switch to 1st approach and start modifying the hbm files and generate db-scripts from them.

telnet protocol impl for scsh

I'm trying to port telnetlib from lisp to scheme for scsh. Code is hosted here and yes, its a work-in-progress, I work on it mostly during the weekend only. Anyway, from this exercise I've certainly observed following...

• Lisp is just so feature rich. Its taking many workarounds to (almost)direct port telnetlib from lisp to scheme.


• Domain knowledge is important. I always thought it was easy to understand the domain and I could just start with anything and I started this project without knowing much about telnet protocol itself and Now I realise that to do it I *have* to understand the nuances of it.

[Update] Its completed.

running cygwin bash within emacs

I've used cygwin on windows for a long time and I don't like the cygwin interface that much. So, I decided to run cygwin bash from within emacs. I put following(found here) in my emacs init file:

(defun cygwin-shell ()
  "Run cygwin bash in shell mode."
  (interactive)
  (let ((explicit-shell-file-name
          "C:/path/to/cygwin/bin/bash"))
    (call-interactively 'shell)))

Now, I can do "Meta-x cygwin-shell RET" to run bash inside emacs and get all the editing power of emacs :) .
PS: Don't forget to append "C:/path/to/cygwin/bin/" to PATH or else most of the commands like ls, grep etc would not work.