Функциональное программирование Лекция 11. Содержание Анализ искусственных и естественных языков Метапрограммирование: Quotations 2. - презентация

1 Функциональное программирование Лекция 11

2 Содержание Анализ искусственных и естественных языков Метапрограммирование: Quotations 2

3 3 Анализ искусственных и естественных языков

4 4 Языки и грамматики Язык – множество слов в алфавите A L A* Может задаваться Перечислением Правилами построение – грамматикой Пример: 1 0

5 5 Контекстно-свободная грамматика Грамматика, в которой применяемое правило не зависит от контекста т.е. по текущему токену можно однозначно определить применяемое правило

6 6 Простой функциональный язык (ПФЯ) Применение функций записывается как f.x Для арифметических выражений не делается исключений Не рассматриваем списки, типы данных и т.д. Язык эквивалентен рассмотренным выше абстрактным деревьям выражений letrec fact = fun x -> if if.. < x 1 then 1 else.. * x (. fact (.. - x 1)) in. fact 5

7 7 Грамматика простого функционального языка (ПФЯ) Expr AppList AppList SimpleExpr | AppList. SimpleExpr SimpleExpr Id | Int | + | - | * | / | | = …. fun id -> Expr ( Expr ) If Expr then Expr else Expr let id = Expr in Expr letrec id = Expr in Expr

8 8 Общий подход к разбору искусственных языков Текст программы (последовательность символов) Лексический анализ Последовательность токенов (FUN,ID,->,…) Синтаксический анализ Синтаксическое дерево Lam(x,App(…)) Интерпретация Компиляция...

Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательно" title="9 Лексический анализ let prog = ReadLines "test.lang" |> Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательно" class="link_thumb"> 9 9 Лексический анализ let prog = ReadLines "test.lang" |> Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательность токенов разбиением на слова Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательно"> Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательность токенов разбиением на слова"> Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательно" title="9 Лексический анализ let prog = ReadLines "test.lang" |> Seq.map_concat(fun x -> x.Split([|' '|])) |> Seq.filter(fun s -> s"") |> Seq.to_list;; В общем случае строится на основе конечного автомата Для простого языка мы можем построить последовательно">

let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let" title="10 Синтаксический разбор методом рекурсивного спуска let rec parse x = match x with "letrec"::id::"="::T1 -> let (tr1,rem) = parse T1 in match rem with "in"::T2 -> let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let" class="link_thumb"> 10 10 Синтаксический разбор методом рекурсивного спуска let rec parse x = match x with "letrec"::id::"="::T1 -> let (tr1,rem) = parse T1 in match rem with "in"::T2 -> let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let (t,r) = parse T in (Lam(id,t),r) | "("::T -> let (t1,r1) = parse T in match r1 with ")"::T1 -> (t1,T1) | _ -> err | " (PFunc(" let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let"> let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let (t,r) = parse T in (Lam(id,t),r) | "("::T -> let (t1,r1) = parse T in match r1 with ")"::T1 -> (t1,T1) | _ -> err | " (PFunc(""> let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let" title="10 Синтаксический разбор методом рекурсивного спуска let rec parse x = match x with "letrec"::id::"="::T1 -> let (tr1,rem) = parse T1 in match rem with "in"::T2 -> let (tr2,T3) = parse T2 in (Let(id,tr1,tr2),T3) | _ -> err | "fun"::id::"->"::T -> let">

11 11 Использование специализированных утилит В комплекте с F# идут классические утилиты для построения компиляторов: fslex – генерация лексического анализатора fsyacc – генерация синтаксического анализатора В обоих случаях по исходным файлам с описанием грамматики строятся программы на F#

12 12 Лексический анализатор { open System open Pars open Lexing } let digit = ['0'-'9'] let whitespace = [' ' '\t' ] let newline = ('\n' | '\r' '\n') rule token = parse | whitespace { token lexbuf } | newline { token lexbuf } | "let" { LET } | "letrec" { LETREC } | "fun" { FUN } | "in" { IN } | "if" { IF } | "then" { THEN } | "else" { ELSE } | "(" { LPAREN } | ")" { RPAREN } | "+" { PLUS } | "-" { MINUS } | "*" { TIMES } | "/" { DIV } | "=" { EQ } | "->" { ARROW } | "." { DOT } | "" { MORE } | ";" { SEMI } | ['a'-'z']+ { ID(lexeme lexbuf) } | ['-']?digit+ { INT (Int32.Parse(lexeme lexbuf)) } | eof { EOF } " { ARROW } | "." { DOT } | "" { MORE } | ";" { SEMI } | ['a'-'z']+ { ID(lexeme lexbuf) } | ['-']?digit+ { INT (Int32.Parse(lexeme lexbuf)) } | eof { EOF }">

13 13 Синтаксический анализатор %{ open Ast %} %start start %token ID %token INT %token LET LETREC FUN IN LPAREN RPAREN IF THEN ELSE SEMI EOF PLUS MINUS TIMES DIV EQ ARROW DOT LESS MORE %type start % start: Prog { $1 } Prog: Expr { $1 } SimpleExpr: | ID { Var($1) }| INT { Int($1) } | PLUS { PFunc("+") } | MINUS { PFunc("+") } | TIMES { PFunc("*") }| LESS { PFunc("") }| DIV { PFunc("/") } | FUN ID ARROW Expr { Lam($2,$4) } | LPAREN Expr RPAREN { $2 } | IF Expr THEN Expr ELSE Expr { Cond($2,$4,$6) } | LET ID EQ Expr IN Expr { Let($2,$4,$6) } | LETREC ID EQ Expr IN Expr { LetRec($2,$4,$6) } Expr: AppList { $1 } AppList: | SimpleExpr { $1 } | AppList DOT SimpleExpr { App($1,$3) }

14 14 Что мы получили? Реализацию простейшего функционального языка программирования! Лексический анализатор Синтаксический анализатор (парсер) Интерпретатор (eval/apply) или реализация с абстрактной SECD-машиной

15 15 Метапрограммирование: Quotations

16 16 Метапрограммирование Метапрограммирование – написание компьютерных программ, которые манипулируют другими программами как данными Реализация «надстройки» языка программирования Трансляция фрагмента кода программы в другое представление Генерация и последующее выполнение кода во время выполнения Метапрограммирование в F# Quotations (цитаты) Computational Expressions (монады)

17 17 Quotations Возможность работать с внутренним представлением фрагментов F#-программы - typed, внутри производится проверка типов - untyped (raw), проверка типов не производится val it : Expr = Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32), [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32), [Value (1), Value (2)]), Value (3)]) {Type = System.Int32;}

18 18 Пример: стековый калькулятор Построим преобразователь арифметических выражений в программу простейшей стековой машины type Command = Push of int | Add | Sub | Mult | Div | Print ;; type Prog = Command list;;

0 then Add::l else if Op.ToString().In" title="19 Работа с Raw Quoations let rec compile l E = match E with Call(_,Op,Args) -> compileop (compilel l Args) Op | Value(x,_) -> Push(int(x.ToString()))::l and compileop l Op = if Op.ToString().IndexOf("Addition")>0 then Add::l else if Op.ToString().In" class="link_thumb"> 19 19 Работа с Raw Quoations let rec compile l E = match E with Call(_,Op,Args) -> compileop (compilel l Args) Op | Value(x,_) -> Push(int(x.ToString()))::l and compileop l Op = if Op.ToString().IndexOf("Addition")>0 then Add::l else if Op.ToString().IndexOf("Mult")>0 then Mult::l else if Op.ToString().IndexOf("Sub")>0 then Sub::l else if Op.ToString().IndexOf("Div")>0 then Div::l else l and compilel l = function [] -> l | h::t -> compilel (compile l h) t;; Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32), [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32), [Value (1), Value (2)]), Value (3)]) compile [] val it : Command list = [Mult; Push 3; Add; Push 2; Push 1] compile [] val it : Command list = [Add; Mult; Push 3; Push 2; Push 1] 0 then Add::l else if Op.ToString().In"> 0 then Add::l else if Op.ToString().IndexOf("Mult")>0 then Mult::l else if Op.ToString().IndexOf("Sub")>0 then Sub::l else if Op.ToString().IndexOf("Div")>0 then Div::l else l and compilel l = function [] -> l | h::t -> compilel (compile l h) t;; Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32), [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32), [Value (1), Value (2)]), Value (3)]) compile [] val it : Command list = [Mult; Push 3; Add; Push 2; Push 1] compile [] val it : Command list = [Add; Mult; Push 3; Push 2; Push 1]"> 0 then Add::l else if Op.ToString().In" title="19 Работа с Raw Quoations let rec compile l E = match E with Call(_,Op,Args) -> compileop (compilel l Args) Op | Value(x,_) -> Push(int(x.ToString()))::l and compileop l Op = if Op.ToString().IndexOf("Addition")>0 then Add::l else if Op.ToString().In">

select (fun c -> c.ContactName) let q = db.Customers |> where c.City =" title="20 Работа с данными и DLinq Цель: использовать функциональный подход для работы с данными из реляционной БД let q = db.Customers.to_array() |> where (fun c -> c.City = "London) |> select (fun c -> c.ContactName) let q = db.Customers |> where c.City =" class="link_thumb"> 20 20 Работа с данными и DLinq Цель: использовать функциональный подход для работы с данными из реляционной БД let q = db.Customers.to_array() |> where (fun c -> c.City = "London) |> select (fun c -> c.ContactName) let q = db.Customers |> where c.City = |> select Работа с данными происходит в памяти Не используются возможности по оптимизации запросов СУБД Использование Query Expression позволяет транслировать такой запрос в SQL и выполнять его на стороне СУБД SELECT ContactName FROM Customers WHERE City = "London" select (fun c -> c.ContactName) let q = db.Customers |> where c.City ="> select (fun c -> c.ContactName) let q = db.Customers |> where c.City = "London" @> |> select c.ContactName @> Работа с данными происходит в памяти Не используются возможности по оптимизации запросов СУБД Использование Query Expression позволяет транслировать такой запрос в SQL и выполнять его на стороне СУБД SELECT ContactName FROM Customers WHERE City = "London""> select (fun c -> c.ContactName) let q = db.Customers |> where c.City =" title="20 Работа с данными и DLinq Цель: использовать функциональный подход для работы с данными из реляционной БД let q = db.Customers.to_array() |> where (fun c -> c.City = "London) |> select (fun c -> c.ContactName) let q = db.Customers |> where c.City =">