В чем преимущества letrec как функции языка программирования

Question

Я посмотрел на все, что я могу найти о letrec, и я до сих пор не понимаю, что он привносит в язык как функцию. Кажется, что все, что можно выразить с помощью letrec, можно так же легко написать как рекурсивную функцию. Но есть ли причины выставлять letrec как особенность языка программирования, если язык уже поддерживает рекурсивные функции? Почему несколько языков выставляют оба?

Я понимаю, что letrec может использоваться для реализации других функций, включая рекурсивные функции, но это не имеет отношения к тому, почему он сам должен быть функцией. Я также читал, что некоторые люди находят его более читабельным, чем рекурсивные функции в некоторых списках, но опять-таки это не актуально, поскольку разработчик языка может приложить усилия, чтобы сделать рекурсивные функции достаточно читабельными, чтобы не нуждаться в другой функции. Наконец, мне сказали, что letrec позволяет более кратко выразить некоторые виды рекурсивных значений, но я пока не нашел мотивирующего примера.

Answer 1

TL;DR: define является letrec, Это то, что позволяет нам писать рекурсивные определения в первую очередь.

Рассматривать

let fact = fun (n => (n==0 -> 1 ; n * fact (n-1)))

К какому объекту относится имя fact внутри тела это определение относится? С let foo = val, val определяется в терминах уже известных объектов, поэтому он не может ссылаться на foo который еще не определен. С точки зрения объема это можно сказать (и обычно так), что RHS let Уравнение определяется во внешнем объеме.

Единственный путь для внутреннего fact на самом деле указать на тот, который определяется, это использовать letrec где определяемый объект может ссылаться на область, в которой он определяется. Таким образом, хотя определение объекта во время его определения является ошибкой, сохранение ссылки на его (будущее, на данный момент) значение вполне допустимо - в случае использования letrec то есть.

define вы ссылаетесь, это просто letrec под другим именем. В схеме тоже.

Без возможности определения сущности для ссылки на себя, т.е. на языки с нерекурсивным let Чтобы иметь рекурсию, нужно прибегнуть к использованию тайных устройств, таких как y-комбинатор. Что громоздко и обычно неэффективно. Другим способом являются такие определения, как

let fact = (fun (f => f f)) (fun (r => n => (n==0 -> 1 ; n * r r (n-1))))

Так letrec сводит к минимуму эффективность реализации и удобство для программиста.

Тогда возникает вопрос, зачем выставлять нерекурсивный let? Haskell действительно нет. Схема имеет как letrec а также let, Одной из причин может быть полнота. Другой может быть более простой реализацией для let с меньшим количеством самоссылочных структур во время выполнения, облегчающих работу сборщика мусора.

Вы просите мотивационный пример. Подумайте об определении чисел Фибоначчи в виде само-ссылочного ленивого списка:

letrec fibs = {0} + {1} + add fibs (tail fibs) 

С нерекурсивным let еще одна копия списка fibs будет определен для использования в качестве входных данных для функции поэлементного сложения add, Что приведет к определению другой копии fibs для этого, чтобы быть определенным в его терминах. И так далее; доступ к n- му числу Фибоначчи приведет к созданию и ведению цепочки из n-1 списков во время выполнения! Не красивая картинка.

И это при условии, что то же самое fibs был использован для tail fibs также. Если нет, все ставки сняты.

Что нужно, так это fibs использует себя, ссылается на себя, поэтому поддерживается только одна копия списка.

Answer 2

NB. Хотя это не специфическая проблема Схемы, я использую Схему для демонстрации различий. Надеюсь, вы можете прочитать немного кода LISP

letrec это просто особенный let где сами привязки определяются до того, как выражения, представляющие их значения, будут оценены. Вообразите это:

(define (fib n)
  (let ((fib (lambda (n a b) 
               (if (zero? n) 
                   a 
                   (fib (- n 1) b (+ a b))))))
    (fib n))

Этот код не работает с тех пор как fib существует в теле let оно существует в замыкании, которое оно определяет, поскольку привязка не существовала, когда вычислялась лямбда Чтобы исправить это letrec на помощь приходит

(define (fib n)
  (letrec ((fib (lambda (n a b) 
                  (if (zero? n) 
                      a 
                      (fib (- n 1) b (+ a b))))))
    (fib n))

Тот letrec это просто синтаксис, который делает что-то вроде этого:

(define (fib n)
  (let ((fib 'undefined))
    (let ((tmp (lambda (n a b) 
                 (if (zero? n) 
                     a 
                     (fib (- n 1) b (+ a b))))))
      (set! fib tmp))
    (fib n)))

Так что здесь вы четко видите fib существует, когда вычисляется лямбда, и позднее привязка устанавливается на само замыкание. Привязка такая же, только ее указатель изменился. Это круговая ссылка 101..

Так что же происходит, когда вы делаете глобальную функцию? Ясно, что если он должен повторяться, он должен существовать до того, как лямбда будет оценена, или среда должна быть мутирована. Здесь нужно исправить ту же проблему.

В реализации функционального языка, где мутация не в порядке, вы можете решить эту проблему с помощью Y (или Z) комбинатора.

Если вам интересно, как реализованы языки, советую начать со статей Мэтта Майтса.