Haskell - определить множество свободных и ограниченных переменных функции

Question

Я должен определить множество свободных и ограниченных переменных функции s1 и s2:

s1 := \x -> if y then \z -> (x \y -> y) else (\z -> w) x

Итак, для s1 я напишу:

FV(s1):= FV (y) ∪ FV (x) ∪ FV (w)

Я прав? Или это должно быть:

FV(s1):= FV (y) ∪ FV (x) ∪ FV (y) ∪ FV (w) ∪ FV (x)

так как у и х два раза свободны. Один раз y в If, а затем результат -> y и для x: x свободен один раз в результате \z и второго в конце.

Ограниченные переменные будут:

BV(s1):= BV (x) ∪ BV (z) ∪ BV (y) ∪ BV (z)

так как z встречается дважды как ограниченная переменная.

Таким же образом я бы определил FV и BVs2:

s2 := let f x1  x2 = y1  (\x -> x2) in let y1 = f w (f y2  y2), y2 = y1  in f

FV(s2):= FV (y1) ∪ FV (x2) ∪ FV (w) ∪ FV (y1)

BV(s2):= BV (f) ∪ BV (x1) ∪ BV (x2) ∪ BV (x) ∪ BV (y1)

Не могли бы вы сказать мне, прав я или нет?

заранее спасибо

Answer 1

Общая идея: привязка к свободным переменным

Практическое правило для свободных и связанных переменных заключается в том, что значение свободной переменной влияет на значение выражения.

Для простого примера, если я определил identity x = x и отдельно сказал x = 6, это не изменило бы тот факт, что identity 10 является 10; в identity x = x переменная x связан, потому что он просто обозначает любой вход, который есть. Мы можем написать identity y = y без изменения значения функции.

И наоборот, если мы определим gimmez x = z, z не связан Если мы отдельно скажем z = 6 затем gimmez делает что-то совсем другое, если мы сказали z = putStrLn "zed zed zed zed can you tell I'm British?", или же gimmez x = zz, В любом случае функция gimmez изменилось - z не был связан

Могу ли я найти и заменить varname за othervarname не меняя смысла?

• Да - varname связан.
• Нет - varname появляется свободно в выражении.

---

Давайте посмотрим на ваши реальные примеры

Пример 1

s1 := \x -> if y then \z -> (x \y -> y) else (\z -> w) 

Вы написали FV(s1):= FV (y) ∪ FV (x) ∪ FV (w) или же FV(s1):= FV (y) ∪ FV (x) ∪ FV (y) ∪ FV (w) ∪ FV (x)

Давайте посмотрим на все переменные по очереди

• Начальный \x -> связывает x для объема лямбда - до конца строки. Это не бесплатная переменная вообще.
• y бесплатно после if, но в недопустимом выражении (x \y -> y), Второе вхождение в этой скобке имеет значение связанной y, а не свободной. Это стирание в противном случае свободной переменной называется затенением. y свободен в выражении, но только благодаря своему первому появлению.
• z связан в конечном лямбда-выражении.
• w никуда не связан - это бесплатно.

Резюме: y а также z Бесплатно. x а также z связаны, y затенено - это также встречается как связанная переменная позже в выражении. FV(s1) = {y,z}, а также BV(s1)={x,z,y}

нотация

Я не согласен с использованием обозначения FV(s1):= FV (y) ∪ FV (w), Это говорит о том, что для поиска свободных переменных s1 Я должен смотреть на свободные переменные y а также w, Я не согласен - y а также z свободные переменные s1, Это правда, что если бы я хотел получить свободные переменные модуля, в котором s1 определяется, мне нужно добавить FV (y) ∪ FV (w), но это другой вопрос.

(Обозначение ∪ указывает на объединение. Вещи находятся в наборе или вне его, вам не нужно добавлять их несколько раз.)

Пример 2

s2 := let f x1  x2 = y1  (\x -> x2) in let y1 = f w (f y2  y2), y2 = y1  in f

let f x1 x2 = связывает f, x1 а также x2, даже если f чувствует себя иначе; все они вводят новую переменную, которая затеняет любое внешнее определение с тем же именем, а поиск и замена их в выражении не изменит его значения, поэтому они связаны.

• f, x1, x2 связаны let,
• y1 бесплатно первый раз появляется - второй let привязка здесь не входит.
• x связан лямбда
• y1 связан let сейчас (больше тени)
• w это бесплатно
• y2 сначала выглядит свободно, но на самом деле ретроспективно связано в выражении y2 = y1

FV(s2):= {y1, w}
BV(s2):= {f, x1, x2, x, y1, y2}