Lattakia1 Lattice Kiaugh Language Reference Manual Heba Elfardy hme2110 Li Yifan yl2774 Dara Hazeghi dmh2186 Wael Salbum wss2113 Why Lattakia Lattakia is a programming language that deals with all the lattice kiaugh kiaugh means trouble or anxiety It s designed to focus on using lattices as a main data structure and code structure In fact Lattakia work on word lattices which are special kinds of lattices partially ordered sets An example of a word lattice is http www statmt org moses n Moses WordLattices Word lattices are powerful representation models They are used in many applications e g in NLP they are useful wherever there is ambiguity uncertainty in the meaning or interpretation of a word such as in speech recognition machine translation language or dialect identification language models paraphrasing e g in information retrieval and question answering and other applications However many researchers avoid using them because they are hard to implement instead they use top n paths Recently many free NLP tools that accept lattices as input have been implemented e g Moses SRILM etc thus we will build a programming language that allows programmers to build lattices process them and provide them to other tools 1 Lattakia or Latakia is a city on the Mediterranean Sea that is over 4000 years old It was called Ramitha and was a part of the kingdom of Ugarit Later under the Roman rule it was called Laodicea Table Of Contents Why Lattakia 1 Table Of Contents 2 Introduction to Word Lattices 3 Defining the language 3 Variables or alternative lattices or altlats 3 Lattices or sequence lattices or seqlats 3 Labels 4 Conditions are also lattices 4 Types Operators and Expressions 5 Assignment and Evaluation 5 Left preference assignment V S Right preference assignment 5 Operations on Lattices 5 Example Stack 6 Constrained Variables Functions 7 Types Of Variables 7 Recursion 7 Epsilon V S NIL 8 Loops built in recursive functions 8 Built in Aggregation functions 9 Example Quicksort 9 Advanced Data Structures 11 Lists 11 Stack and Queue 11 Hash Tables 11 Sets 11 Tuples 11 Search and Rule Triggering 12 Search Regular Expressions 12 Rules When triggered condition satisfied apply action 12 Accessing the value of a variable Not part of our plan for this semester 12 Example Part of Speech POS Tagger 13 Object Oriented Lattakia Under construction 14 Classes 14 Objects 14 Inheritance Start from the general to the specific 14 Generalization Start from the specific to the general 15 Introduction to Word Lattices Defining the language 1 Atom definition an atom is any expression as in other programming languages such as assignment mathematical expressions conditions function calls etc 2 Word lattice definition 1 An atom is a lattice 2 lattice lattice is a lattice we call it alternative lattice or altlat 3 lattice lattice is a lattice we call it sequence lattice or seqlat In this language both data and code are written in this lattice format To represent the lattice in a way similar to other programming languages we think of a lattice as an array of variables where variables can have multiple values For example if we want to build a Part Of Speech POS tagger for in following example we need to give variables multiple values Time flies N V Adj N V 1 N V Adv 2 Adj N V 3 V N Adv like an arrow V Adv Det N Det N Det N Det N Variables or alternative lattices or altlats A variable can have multiple values at the same time a 5 x 3 7 2 isImportant x 75 false x 75 true isEmptyStack stack epsilon true false Notice that isImportant and isEmptyStack are variables here while they are functions in other programming languages x is called an independent variable while isImportant is called an dependant variable because it depends on x Lattakia is a language that handles this kind of variables INDEXING To access the second value of x which is 7 x 1 As in C index start from 0 Lattices or sequence lattices or seqlats An array of this kind of variables is actually a lattice yLat v1 v2 v3 v1 4 v2 x v3 a 2 yLat 4 x a 2 INDEXING To access the second value of yLat which is x yLat 1 As in C index start from 0 Note that are used for alternative lattices while are used for sequence lattices We call a variable an alterntives lattice or altlat because a variable with multiple values is a lattice of multiple alternatives In contrast we call a lattice a sequence lattice or seqlat Examples The following lattices are shown in the figures below lat0 A lattice with an epsilon transition i e an empty lattice lat1 load file1 lat load is a optimized built in function to read a lattice from a file in our format lat2 a b1 b21 b22 b3 c11 c12 c2 lat3 a b 3 b1 b 0 b21 b22 b3 c11 c12 c2 lat2 1 1 b2 lat3 1 1 0 b21 3 Labels latLab l1 a l2 b1 b2 Labels are actually similar to labels in other programming languages they are names assigned to be used later Think of labels here as variable handles or names of the nodes When accessing a label you actually get the variable that comes after this label s node Labels can be used later to access variables inside the lattice Labels represent keys in hash tables and fields in objects To access a label from inside it s lattice you just need to use it s name To access a label from outside it s lattice you need to use the operator x latLab l2 Conditions are also lattices a 4 b 3 b 4 b 2 0 c or a 4 b 3 b 4 b 2 0 c Think of it as this is a list of conditions that must be satisfied Or think of it as a lattice of epsilons on the arcs guarded by these conditions as shown in the figure below Types Operators and Expressions Assignment and Evaluation y 3 The r value is a constant y s value is 3 yIsEven y 2 0 yIsEven is assigned the equation not the current value y 2 0 is not evaluated here i e when y changes yIsEven changes too Here there is no problem if y is not initialized This is as defining functions in programing languages the only difference is that they look at it form an Assembly perspective a function is a routine or procedure that returns a value while we look at it from a mathematical perspective variable yIsEven is a function of variable y x y 3 or x y 3 The operator takes one operand to the left and evaluates it Here the value of x is 3 3 6 z y 2 x Here z is a function of x but not of y z 3 2 x w z x y The operator evaluates the r value and assigns it to the l value The assigment statement evaluates to its l value x y 3 x …
View Full Document
Unlocking...