Skip to content

Latest commit

 

History

History
90 lines (75 loc) · 6.28 KB

Funky.md

File metadata and controls

90 lines (75 loc) · 6.28 KB
Raw

Funky

Как да си напишем интерпретатор?

Каква е целта? Получваме низ и връщаме резултат. Резултатът няма да е случаен, а ще е следствие на "изчислението" или "оценката" на низа. Низът от своя страна има структура и следва някакви правила. Работата на интерпретатора грубо може да разделим на два големи етапа - откриването на тази структура в самия низ -parsing, и изпълнението/oценяването - execution/evaluation. Ще се фокусираме само върху втората операция.

1. Аритметични операции

Да разгледаме най-простия израз "2+22". Kак може да го обработим? След като сме го parsе-нали, сме получили готова структура. Каква може да бъде тази структура? Един вариант е например да са два списъка numbers :: [Int] и operations::[Char]. Да видим дали не може да се справим по-добре с ADT:

data Expression = Add Int Int

Операцията + я представяме с конструктура Add. Функцията, която оценява израза, ще изглежда по-следния начин:

eval :: Expresion -> Int
eval (Add x y) = x + y

Сега вече може да сметнем 2+22, но може ли да смятаме произволни изрази 2+3+4, (2+2)+2+2. Ако разгледаме по-внимателно (1+2) + (3+4), може да видим, че е съставен от рекурсивни подизрази и да променим Expression да отразява това:

data Expression = AddI Int Int | AddE Expression Expression

А еval става:

еval (AddI x y)   = x + y
eval (AddE ex ey) = eval ex + eval ey

Сега вече може да смятаме неща като 1+2, (1+2)+(2+1), но все още не `1 + (2+2)``. Лесно може да решим проблем с

data Expression = AddII Int Int
                | AddEE Expression Expression
                | AddIE Int Expression
                | AddEI Expression Int

Всъщност туко-що написахме всички възможни комбинации за две елемента между Expression и Int. Може ли да го съкратим? След доста взиране, може да видим, че това е възможно, като накараме просто число (4 например) само по себе си да е Expression - например като Constant Int. Taка Expression и eval добиват вида:

data Expr = Constant Int
          | Add Expr Expr

eval :: Expr -> Int
eval (Constant x)     = x
eval (Add left right) = eval left + eval right

Aналогично може да добавим и другите аритметични операции.

Забележка: Какво става със скобите в изрази и как ги поддържаме? В момента искаме да изчисляваме данни от тип Еxpression, например Add (Const 3) (Add (Const 5) (Const 2)). Работа на parser-а е да преобрузава стрингa "3 + (5+2)" до тази репрезентация.

2. Променливи

Нека да добавим и променливи. Отново да започнем с най-простия случай:

x = 2
1 + x

Какво операции относно променливите имаме? Две основни - декларацията (x = 2) и използването в израз (1 + x). Реално самата декларация не е израз, който връща някакъв резултат като число и моделира изчисление. Да си направим ново ADT за нея: data VarDecl = VarDecl String Expr.

Използването на променлива обаче е израз. Така Expression става:

data Expr = Constant Int
          | Var String
          | Arith ArithOp Expr Expr

Резултът от декларацията на променливата е, че вече елементът x ще асоциираме със стойността 2. Tрябва някъде да запазим тази инфорамция. Да си дефинираме променлива scope :: [(String, Int)], която ще държи тези двойки. Такива променливи обикновено наричаме среда (в която ще се случва изчислението). Освен това самата ни програма вече не е прост израз, а е последователност от такива декларации и израз най-накрая: data Program = Program [VarDecl] Expr

Първо да си напишем нова функция, която изпълнява програмата. Освен да оценява израза, ще трябва да обработва дефинициите на променливи и променя средата. След това да променим eval така че да може да оценява променливи и да се съобразява с текущата среда.

runProgram :: Program -> Int
runProgram (Program decls body) = eval (mkScope [] decls) body
    where mkScope sc []                       = sc
          mkScope sc (VarDecl name expr : xs) = mkScope ((name, eval sc expr):sc) xs

mkScope е помощната функция, която създава средата.

eval :: Scope -> Expr -> Int

eval scope (Var name) = unbox (lookup name scope)
    where unbox (Just val) = val
          unbox Nothing    = error ("Varible `" ++ name ++ "` not found!")

eval _   (Constant x) = x
....