Week 2 Notes

Fluent APIs | CS 3040

Sequences | Sequential Solution

turnstile = new Fsm();
State s = new State();
s.setStateId("locked");
s.setInitial(true);
turnstile.getStates().add(s);

...

Functional solution

turnstile = new Fsm();
turnstile.getStates().add(new State("locked", true));
turnstile.getStates().add(new State("unlocked"));

...

• Less focus on sequencing
• Still has problems:
  • Lots of object construction
  • Heavy container manipulation
  • Repetitive
• Solution: a fluent API

Fluent API

• Using factory methods rather than constructors to build objects.
• Using method chaining: each step returns object that can be applied, which is an application of the Builder pattern.
• Implicit parameters: in this case, a "current state" so no need to repeat.
• Provide useful conventions to eliminate boilerplate code.

turnstile = fsm()
.addState("locked")
	.addTransition("ticket", "collect", "unlocked")
	.addTransition("pass", "alarm", "exception")
.addState("unlocked")
	.addTransition("ticket", "eject", "unlocked")


...

• Eliminate boilerplate code
  • i.e. Assume first state is the initial state

Developing a fluent API for a language

1. Write/select sample programs in the target language
2. Design objects with factory methods constructing domain objects
3. Add methods matching target language actions
   • Most operations will be applied to a current object, possible updating it
   • Most methods will return the current object
4. Identify initial states, implicit information from one to next

Internal DSL

Domain specific language - solution just using existing programming tools

External DSL

Building a new language for the domain

• Allows for non-developers to build, verify models

Run Method: Interpreter

public class FsmlInterpreter {
	public static String[] run(Fsm fsm, String[] input) {
		ArrayList<String> output = new ArrayList<>();
		String state = fsm.getInitial();
		for (String event : input) {
			ActionStatePair pair = fsm.makeTransition(state, event);
			if (pair.action != null) output.add(pair);
			state = pair.state
		}
		return output.toArray(new String[output.size()]);
	}
}

Syntax

Fluent API for internal DSL

Semantics

Interpreter describes what happens when executing syntax

Well-formedness

Checking this is resasonable

• No two states have the same ID
• One initial state
• Each state pair has at most one transition
• Each transition goes to a declared state
• No state not reachable from the initial state

External DSL

• Basic tool: develop a language around the problem
• Langauge specification

fsm : {state}* ;
state : {'initial'}? 'state' stateid '{' {transition}* '}' ;
transition : event {'/' action}? {'->' stateid}? ';' ;
stateid : name ;
event : name ;
action : name ;

• Sample construction
• A FSM is a sequence of states, one marked intial
• Each state has an action, result, and transition to new state
• States, events, actions: text
• No transition: stay in same state

Implementing the External DSL

• ANTLR
• Another Tool for Language Recognition
• Basic goal: support compiler generation
• Essentially, a domain-specific language for compiler writers!

External DSL | CS 3040

• Domain specific languages in general

  • Computer langauge targeted at a specific domain
  • In contrast to general purpose langugages like Python, C

• Examples

  • HTML, YAML, other markup languages
  • JSON
  • SQL
  • Build scripts (make, Docker, ANT)
  • Command prompt software
  • MATLAB, Mathematica, Maple - symbolic math
  • Csound: sound and music synthesis
  • Terraform: manage cloud servers, network appliances
  • Level specifiers for computer games
  • Security, process tools

• Next: Regular Expressions

Problem: how would I search for all of the uses of "int" in a program?

• Issue: the text can appear in many contexts
• Can't just search for "int" - would pick up "pint" or "int_32"
• Regular expressions look for patterns

Regular Expressions

• a way to define sets of strings
  • a = { a }
  • b = { b }
  • ab = -- sequence { ab }
  • c | d = -- choice { c, d }
  • a (b | c) = { ab, ac }
  • a^5 = -- repetition { aaaaa }
  • a* = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, ... }

Precedence

• Parenthesis groups items

• Star has highest precedence

• Concatentation (xy) has next precedence

• alternation (x|y) has the lowest precedence

• Strings of 0's and 1's with at least one 1

  • 1(0|1)*

• Strings of a's and b's with at least 3 consecutive a's in them

  • (a|b)* aaa(a|b)*

• strings of a's and b's with at least 3 a's in them (anywhere)

  • b* a b* a b* a (a | b)*

• strings of a's and b's with no doubled a's or b's

  • (E|b)(ab)* (a|e)

RegEx | CS 3040

Shorthand

x+ | xx* = 1 or more, x* = 0 or more

Ignoring case

• In some cases there's a switch; e.g.: -i on egrep ignores case

Ranges

• [uvw] instead of (u | v | w)
• [k-n]
• [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• [a-zA-Z0-9]

Searching for array expressions in code Example:

egrep \[[0-9a-zA-Z_]*\] *.cpp

Other

• ^ forces a match at the beginning
• $ forces a match at the end

Regular Expressions in ANTLR
General rules:
        VARIABLE: regular expression ;
Any text to be matched: in quotes
        SALUTATION: 'Hello';
With alternative:
        SALUTATION: 'Hello' | 'Hi' | 'Greetings,';
Dot: any character
        ANY: .;
Parens: group
Range: ..
        DIGIT: '0'..'9';
        LETTER: ('A'..'Z') | ('a'..'z');
Range with other characters:
        IDENTIFIER_CHARACTER: ('a'..'z') | ('A'..'Z') | ('0'..'9') | '_';
Repetition: +, *:
        NUMBER: ('0'..'9')+;
        ID: ('a'..'z')+('0'..'9')*;
Optional:
        MONTH: '1'?('0'..'9');
Negation:
        NON_DIGIT: ~('0'..'9');
... 
- [https://faculty-web.msoe.edu/hasker/cs3040/notes/n02-3040-re.html]

Grammar | CS 3040

Expression Parsing

3 + 4 * 5

• First step: capture the structure (a tree)

Solution: grammars

• Broadly speaking, a grammar describes how programs or "sentences" are structured

  • A sentence is a piece of text to be "parsed"

• Parsing:

  1. Checking to see if a sentence is legal by a grammar
  2. Capturing the structure of the sentence

• Programs: sentences that capture computer instructions

• Utterances in domain-specific languages (DSLs):

  • Sentences which can be interpreted in the domain

• Grammars give us parse trees, parse trees can be interpreted

BTL definition

• Grammar:

Expr -> true
Expr -> false
Expr -> zero
Expr -> succ( Expr )
Expr -> pred( Expr )
Expr -> iszero( Expr )
Expr -> if(Expr, Expr, Expr)

Another grammar: capturing statements in English

• A simple grammar for sentences

SimpleSentence -> Noun Verb Object
Noun -> zoe | sam
Verb -> climb | push | throw
Object -> car | ladder | ball

Where:

• lower case: terminal

• upper case: non-terminal (variable)

• Extend BTL with x = Expr, sequence

• Simplifying: make both into expressions, adding:

Expr -> variable
Expr -> variable = Expr
Expr -> Expr ; Expr

Grammars

• How should we specify a programming language syntax?
• Solution 1: examples -what can go wrong?
• Solution 2: English - what can go wrong with this?
• Classic notation: Backus-Naur Form (BNF), dating to 1959
  • Developed by John Backus to describe Algol 58
  • A way to describe context-free grammars
  • A metalanguage
    • A language used to describe another language
  • In BNF, abstractions are used to represent classes of syntactic structures
    • acting like syntactic variables, generally called nonterminal symbols