LINUX.ORG.RU

Man or boy 2к25: Ваш статически типизированный ЯП полноценен?

 


0

4

Когда то Кнут придумал тест для ALGOL реализаций, и он известен под именем «Man or boy test». Но там просто локальные функции, не особо интересно.

Предоставляю вам версию для проверки языка программирования, на то, достоен ли он существовать в 21 веке!

Для начала нарушу это правило (у Python динамическая типизация), и покажу Python версию:

def print_sum(x):
  def make(acc):
    def f(y):
      print("acc(%d) + %d" % (acc, y))
      return make (acc + y)
    return f
  return make(x)

print_sum(10)(20)(30)(40)
Вывод
acc(10) + 20
acc(30) + 30
acc(60) + 40

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

Мое повторение на OCaml с rectypes:

let print_sum x =
  let rec f acc = fun y ->
    printf "acc(%d) + %d\n" acc y;
    f (acc + y)
  in 
  f x
  
let () = ignore (print_sum 10 20 30 40)
Типы он вывел сам, но можно и указать вручную:
type t = int -> t 

let print_sum (x : int) : t =
  let rec f (acc : int) : t = fun (y : int) : t ->
    printf "acc(%d) + %d\n" acc y;
    f (acc + y)
  in 
  f x
  
let () = ignore (print_sum 10 20 30 40)

Языки которые смогли реализовать тест на лямбдах/функциях, их система типов и ее записи позволяет строить рекурсивные по возврату лямбды и функции:

Языки у которых получилось, но замыкания были выраженны через структуры, потому что они так представленны в самом языке, это облегачает построение рекурсивных по возврату типов, потому что рекурсии в структурах есть везде:

Языки у которых пока не получилось без дополнительных средств типа классов/структур для обхода проблем с типами:

  • Rust (использование trait)
  • C (некорректная реализация)
  • Zig (использование классов)
  • D (использование делегатов)

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

★★★★★

Последнее исправление: MOPKOBKA (всего исправлений: 21)

Типы он вывел сам

Кто «он»?

File "lib/misc.ml", line 159, characters 6-17:
159 |       f (acc + y)
            ^^^^^^^^^^^
Error: This expression has type int -> 'a
       but an expression was expected of type 'a
       The type variable 'a occurs inside int -> 'a
  Hint: This function application is partial,
  maybe some arguments are missing.

можно и указать вручную

File "lib/misc.ml", line 156, characters 2-24:
156 |   type 'a t = 'a -> 'a t
        ^^^^^^^^^^^^^^^^^^^^^^
Error: The type abbreviation t is cyclic:
         'a t = 'a -> 'a t,
         'a -> 'a t contains 'a t
korvin_ ★★★★★
()
Ответ на: комментарий от korvin_

https://ocaml.org/play#code=I3JlY3R5cGVzOzsgKCog0LjQu9C4IC1yZWN0eXBlcyDQutCw0...

Вижу ты знаешь Haskell, у меня на нем не получилось повторить.

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от unDEFER

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

Ну если ты хочешь более реального примера, то пусть будут ленивые cons-ячейки, = ленивый список.

def cons(car, cdr):
  return lambda: [car, cdr]

def car(cons):
  if (x := cons()) is None: return None
  else:
    (car, _) = x
    return car

def cdr(cons):
  if (x := cons()) is None: return None
  else:
    (_, cdr) = x
    return cdr

def map(f, l):
  if (x := l()) is None: return None
  else:
    (hd, tl) = x
    return lambda: (f(hd), map(f, tl))

def slow(x):
  print("slow calculation...", x)
  return x * 2

x = cons(1, cons(2, cons(3, cons(4, cons(5, cons(6, None))))))
y = map(slow, x)
car(cdr(cdr(y)))

Вывод

slow calculation... 1
slow calculation... 2
slow calculation... 3
map обработал только те ячейки, которые мы запросили в последней строке, не трогая 4, 5, 6. Применений этому полно!

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

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

Ну т.е. я правильно понял, что если язык настоящий то в нём подобного бреда (рекурсивного типа) невозможно?

unDEFER ★★★★★
()
Ответ на: комментарий от unDEFER

Все так, но ровно наоборот. Просто представь, человек уже 56 лет как вступил на луну, а где то невозможно описать рекурсивную по возврату функцию.

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от MOPKOBKA

человек уже 56 лет как вступил на луну

Ну вот когда там человек регулярно будет тусить, тогда и заходите с такими запросами, а пока я так и не увидел практической пользы от этого.

А ленивые вычисления у меня в языке есть (D). Но пользовался я ими лишь однажды в задаче, где я ещё и зелёные треды использовал и вычисления над типами во время компиляции.

Автоматически тип функции make() D вывести не смог, да и вручную я не придумал такой делегат, но наверняка получится повторить с классами.

unDEFER ★★★★★
()
Ответ на: комментарий от Psilocybe

Это тест Кнута, а я тут свой придумал. Тест кнута повторяли на многих языках, даже на тех, что не имеют локальные функции, примерно так как unDEFER эмулирует замыкания.

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от flant

Не везде соблюдается/принимается. MISRA и прочие часто критикуются, так как это не позволяет писать выразительный код, и может наоборот приводить к большим ошибкам.

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от MOPKOBKA

Ну помогите немного компилятору, разбейте своё очень длинное выражение на 2 или 3.

Вы же понимаете, что данные приходят в программу из вне, а не хранятся в программе в виде цепочек из скобочек?

В любом случае это просто ограничение компилятора, а не проблема языка.

unDEFER ★★★★★
()
Ответ на: комментарий от unDEFER

Разбил на 3 переменные, все равно ошибка: https://godbolt.org/z/qr9vrGoej

А там память не будет выделяться если в цикл его положить?

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 1)
struct A {
    acc: i64,
}

impl A {
    fn add(&mut self, y: i64) -> &mut Self {
        println!("acc({}) + {}", self.acc, y);
        self.acc += y;
        self
    }
}

fn main() {
    let mut a = A{acc: 10};
    a.add(20).add(30).add(40);
}

Я по сути создал руками структуру замыкания и добавил явный метод вместо неявного. В расте замыкания создают аналогичные анонимные типы, которые нельзя написать или назвать, чтобы на них же сослаться. Говорят в экспериментальных сборках что-то там такое есть, но мне лень ставить найтли чтобы проверить.

Если прям надо каждый раз новое замыкание создавать, то можно вместо возврата self создавать заново A{acc: self.acc}.

neumond
()
Ответ на: комментарий от MOPKOBKA

Поровну делить надо. А вы на третий кусок больше половины оставили.

А там память не будет выделяться если в цикл его положить?

Не знаю, не проверял.

unDEFER ★★★★★
()
Ответ на: комментарий от neumond

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

Ну их же передают / возвращают.

fn returns_closure() -> impl Fn(i32) -> i32 {
    |x| x + 1
}

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от MOPKOBKA

Всё так, но там, где на выходе i32, нужно написать имя типа замыкания, которое нельзя получить. А без явного имени типа там будет бесконечное разворачивание цепочки замыканий.

neumond
()
function print_sum(x)
   function make(acc)
      return function(x)
         print(("acc(%d) + %d"):format(acc, x))
         return make(acc+x)
      end
   end
   return make(x)
end

print_sum(10)(20)(30)(40)
$ lua main.lua 
acc(10) + 20
acc(30) + 30
acc(60) + 40
#include <stdio.h>
typedef void * (*recall)(int x);

recall print_summ(int x)
{
   static int acc = 0;
   acc ? printf("acc(%d) + %d\n",acc,x):0;
   acc+=x;
   return (recall)print_summ;
}

int main(int argc, char *argv[])
{
   ((recall)((recall)((recall)print_summ(10))(20))(30))(40);
   return 0;
}
$ gcc main.c -o app && ./app
acc(10) + 20
acc(30) + 30
acc(60) + 40
LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от LINUX-ORG-RU

Второй пример некорректен, это не замыкание, нельзя повторить вот такое:

function print_sum(x)
   function make(acc)
      return function(x)
         print(("acc(%d) + %d"):format(acc, x))
         return make(acc+x)
      end
   end
   return make(x)
end

x = print_sum(10)(20)(30)(40)
x(100) <--
x(100) <--
acc(10) + 20
acc(30) + 30
acc(60) + 40
acc(100) + 100 <---
acc(100) + 100 <---

Ну и по стандарту конечно нельзя приводить указатель на данные к указателю на функцию.

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

Канешна :( У тебя условия с подставой :) Только так, мимикрируя. Гнутые замыкания толку дёргать нет, их не вернуть. Попозже косплей сделаю на внешних дёрганиях. Тоже не то будет, ну и ладна :) не сооружать же jit или вставки.

LINUX-ORG-RU ★★★★★
()

Раз пошла такая пьянка

#!/usr/bin/env perl

use strict;
use warnings;

sub print_sum {
    sub f {
        my ($acc) = @_;
        sub {
            printf "acc(%d) + %d\n", $acc, $_[0];
            f($acc + $_[0])
        }
    }
    f $_[0]
}

my $x = print_sum(10)->(20)->(30)->(40);
$x->(100);

$ ./print_sum.pl 
acc(10) + 20
acc(30) + 30
acc(60) + 40
acc(100) + 100
annulen ★★★★★
()
Ответ на: комментарий от MOPKOBKA

Вижу ты знаешь Haskell, у меня на нем не получилось повторить.

Может ли Haskell дотянуть по типам до OCaml и C++? Возможно ли там повторить пример?@hateyoufeel

Можно, но надо типы руками описывать. В хачкелле тебе монадки не дадут вот прямо такое один в один переписать.

hateyoufeel ★★★★★
()
Ответ на: комментарий от anonymous

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

з.ы. лямбды - синтаксический сахар. потому что всегда (с начала времён) были функторы и ими все спокойно обходились. потом придумали модное слово и понеслось.

Iron_Bug ★★★★★
()
function printSum(x: number) {
    return (function make(acc: number) {
        return function (y: number) {
            console.log('acc(%o) + %o', acc, y);
            return make(acc + y);
        };
    })(x);
}

printSum(10)(20)(30)(40);
$ bun sum.ts 
acc(10) + 20
acc(30) + 30
acc(60) + 40

А в чём подвох?

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 3)
Ответ на: комментарий от Nervous

Когда коту Морковкина делать нечего, он лижет яйцы.

А когда самому Морковкину делать нечего, он лижет яйцы коту, и придумывает загадки для сумасшедших.

alysnix ★★★
()
(defun print-sum (x)
  (labels ((make (acc)
             #'(lambda (y)
                 (format t "~&acc(~D) + ~D~%" acc y)
                 (make (+ acc y)))))
    (make x)))
CL-USER> (funcall (funcall (funcall (print-sum 10) 20) 30) 40)
acc(10) + 20
acc(30) + 30
acc(60) + 40

;; OR

CL-USER> (reduce #'funcall (list 20 30 40) :initial-value (print-sum 10))
acc(10) + 20
acc(30) + 30
acc(60) + 40
anonymous
()