pergunta Avaliação Idioma: Vs. Eager Preguiçoso

Question

Eu estava lendo PLAI de Shriram e isso eu fiquei preso em estas perguntas:

1. Você pode provar que os regimes ansiosos e preguiçosos sempre produzirá a mesma resposta? (Shriram pede para olhar para a linguagem que ele desenvolvido, mas existe outra maneira de provar isso e como?)

2. avaliação ansiosa sempre reduzir com menos etapas?

Aqui está o Código de Substituição e Avaliação Ansioso em Clojure.

;; Gets W-lang and returns the computed number
;; (evaluate (let x (num 10) (let y x x)) -> 10
;; (evaluate (let x (num 10) (let y (add x (num 10)) y)) ->20
;; (evaluate (let x 10 (let x x x ))) -> 10
;; (evaluate (let x 10 (let x (+ 10 x) 
;;                            (let y (let y (+ 10 x) y)
;;                                   (+ x y))))-> 50

(defn evaluate[W-lang]
  (condp = (first W-lang)
    'num (second W-lang)
    'add (+ (evaluate (second W-lang))
            (evaluate (third W-lang)))
    'sub (- (evaluate (second W-lang))
            (evaluate (third W-lang)))
    'let (evaluate (subst (second W-lang)(third W-lang) 
                          (forth W-lang)))))


;; subst: symbol value W-Lang -> W-lang
;; substitutes the symbol and returns a W-Lang
(defn subst[id value W-lang]
    (cond
      (symbol? W-lang) (if (= id W-lang) value W-lang)
      (seq? W-lang)
      (condp = (first W-lang)
      'num (list 'num (first (rest W-lang)))
      'add (list 'add (subst id value (second W-lang))
                      (subst id value (third W-lang)))
      'sub (list 'sub (subst id value (second W-lang))
                      (subst id value (third W-lang)))
      'let 
      (if (= (second W-lang) id)
        (list 'let (second W-lang) 
                    (subst id value (third W-lang))
                    (forth W-lang))
        (list 'let(second W-lang)
                   (subst id value (third W-lang))
                  (subst id value (forth W-lang))))
      W-lang)))

Answer 1

1. Você não forneceram informações suficientes, mas se Shriram fornece um pequeno-passo semântica, provavelmente você está à procura de uma prova por forte indução sobre o número de passos, ea técnica prova que você quer é provavelmente bissimulação .

2. Quanto ansioso contra preguiçoso, qual é capaz de computação mais desnecessário? Qual deles coloca um limite superior para computação adicional?

Eu tive uma olhada mais recente projecto da Shriram, e ele não bateu realmente semântica até o capítulo 23, e depois é só big-passo semântica. Eu não poderia encontrar onde ele pode mostrar-lhe as técnicas que você precisa para responder às perguntas, a não ser que talvez ele tem em mente para você intérpretes de escrita que contam reduções.

Se você quiser provas, eu não acho que o livro de Shriram é o lugar certo para aprender a técnica de prova para linguagens de programação. O livro de Glynn Winskel nas semântica formal de linguagens de programação é muito bom, mas é bastante avançada. A menos que você está matematicamente sofisticado, que vai ser difícil sem um professor.

Você é provavelmente melhor fora de pular as partes à prova de material de Shriram, ou tentar um livro mais user-friendly como Tipos de Benjamin Pierce e Linguagens de Programação .

---

Disclaimer: Eu escrevi uma programação-línguas livro didático, mas como ele permanece indisponível (eu não consigo terminar o capítulo 8 e obter um projecto para uma editora), ele provavelmente não deve ser visto como a concorrência. Mas um dia ele vai ser: -)

Answer 2

Eu não li o livro em resposta à segunda pergunta, eu diria: não, avaliação ansiosa nem sempre resultar em menos reduções. Com avaliação preguiçosa você pode muito bem evitar ter que fazer alguma computação.