vak | Entries tagged with scala

Удачный язык Scala: хочешь пиши в функциональном стиле, а хочешь - в традиционном процедурном, на выбор. Сравним два стиля на примере упомянутой задачки Two-Sum.

Функциональный стиль, так называемый "однострочник":

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    nums.zipWithIndex.combinations(2).find(_.map(_(0)).sum == target).get.map(_(1))
}

Процедурный стиль:

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    for (j <- nums.indices) {
        for (i <- 0 until j) {
            if (nums(i) + nums(j) == target) {
                return Array(i, j)
            }
        }
    }
    throw Exception("no solution")
}

Какое из этих двух решений легче понять и доработать при необходимости?

Мне по жизни доводилось решать задачки в функциональном стиле. Делали мы однажды девайс для передачи данных, и надо было научить его тестировать линию связи. Для этого на девайсе нажимается кнопочка, и такой же девайс на удалённом конце линии включает "шлейф" - принятые от нас данные заворачивает обратно к нам. Нужен простой способ послать команду удалённому девайсу, не вмешиваясь в основной поток данных. Имелся медленный однобитовый канал out-of-band. Решение было послать по этому последовательному каналу псевдослучайный поток, сформированный сдвиговым регистром с обратной связью (LSFR).

Математически LSFR выглядит как двоичный полином, к примеру x¹⁶+x¹⁴+x¹³+x¹¹+1. Чтобы выбрать подходящий к ситуации полином, я быстренько сбацал код на Scheme, и через час решение было найдено.

Через пару лет мы разработали другое устройство, для гораздо более скоростных линий связи, но с другим характером помех в линии. Старые полиномы больше не подходили: наблюдались ложные срабатывания. Надо было подобрать другие полиномы, подлиннее. Достал я старый код и... убил пару дней, пытаясь в нём разобраться. Плюнул, переписал на Си, и код стал понятным.

Перефразируя Форреста Гампа, это всё, что я могу сказать о моём отношении к функциональному программированию. 😀

Читаю книжку по третьей Скале, всё нравится. Но теория одно дело, а надо же инструментарий освоить. Минимальный набор практических навыков: создать проект, скомпилировать, добавить юнит тесты, протестировать. То, что для Си/Си++ решается через make/cmake/gtest, здесь делается посредством утилиты sbt.

В качестве задачки, чтобы долго не гадать, взял #1 с Leetcode. Есть такой сайт leetcode.com, где предлагается решать программистские задачки на разных языках. Полезно для самообразования, да и работодатели часто дают задания через Leetcode при отборе кандидатов. Задачи там подобраны вполне неплохие. Самая первая из них называется Two-Sum: найти в массиве пару чисел с заданной суммой. Условие смотрите здесь: https://leetcode.com/problems/two-sum/

Scala мне не всякая годится, а только native. Вообще обычно Скалу применяют на виртуальной машине JVM, или через JavaScript в веб-браузере. В моей области всё это не годится. Но есть третий способ: компиляция в native код. Ровно то что нужно (scala-native.org).

Для юнит тестов в Скале есть несколько пакетов, но native работает только JUnit. Нормальная вещь, годится. Подробности здесь: scala-native.org/en/stable/user/testing.html

Собрал я всё это дело в кучу, готовый проект выложил на Гитхабе: two-sum-native. Основная ценность в файлах конфигурации: build.sbt, project/plugins.sbt.

Само решение задачки я честно нагуглил в интернете, маленько приспособив под себя. Вот первый вариант: решение в лоб, медленное, со сложностью O(n²). Зато красивый функциональный стиль. Можно вообще в одну строчку записать, но малопонятно будет. Комментарии мои.

( Исходники )

Оказывается, Скалу теперь можно компилить непосредственно в бинарный код, без всякой Джавы и прочих виртуальных машин. Неплохой язычок получается.

(1) Сначала устанавливаем sbt по инструкции: https://www.scala-sbt.org/1.x/docs/Setup.html

(2) Создаём проект типа "Hello World":

$ sbt new scala-native/scala-native.g8

На запрос надо будет ввести желаемое имя проекта. Я выбрал hello.

(3) Компилируем и запускаем:

$ cd hello
$ sbt run
[info] welcome to sbt 1.6.2 (Ubuntu Java 11.0.17)
[info] loading settings for project hello-build from plugins.sbt ...
[info] loading project definition from /.../hello/project
[info] loading settings for project hello from build.sbt ...
[info] set current project to hello (in build file:/.../hello/)
[info] compiling 1 Scala source to /.../hello/target/scala-3.1.3/classes ...
[info] Linking (1343 ms)
[info] Discovered 663 classes and 3689 methods
[info] Optimizing (debug mode) (1047 ms)
[info] Generating intermediate code (829 ms)
[info] Produced 12 files
[info] Compiling to native code (1583 ms)
[info] Linking native code (immix gc, none lto) (122 ms)
[info] Total (4968 ms)
Hello, world!
[success] Total time: 9 s, completed Nov 21, 2022, 1:11:59 PM

Смотрим исходник:

$ cat src/main/scala/Main.scala 
object Main {
  def main(args: Array[String]): Unit =
    println("Hello, world!")
}

Смотрим бинарник:

$ size target/scala-3.1.3/hello-out 
   text	   data	    bss	    dec	    hex	filename
1625129	 223248	   4928	1853305	 1c4779	target/scala-3.1.3/hello-out

$ ldd target/scala-3.1.3/hello-out 
	linux-vdso.so.1 (0x00007ffe9492a000)
	libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f5817600000)
	libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f5817517000)
	libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f5817895000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f5817200000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f5817a93000)

$ ./target/scala-3.1.3/hello-out 
Hello, world!

Подробности здесь: https://scala-native.org/en/stable/user/index.html

Рождается новый симпатичный язычок для разработки хардвера: Chisel. Порождает код на Verilog, не уступающий по качеству написанному вручную, а также cycle-accurate симулятор на Си++, работающий в восемь раз быстрее чем Synopsys VCS. Сделан на основе языка Scala. Пример кода:

import Chisel._

class GCD extends Module {
  val io = new Bundle {
    val a  = UInt(INPUT,  16)
    val b  = UInt(INPUT,  16)
    val e  = Bool(INPUT)
    val z  = UInt(OUTPUT, 16)
    val v  = Bool(OUTPUT)
  }
  val x  = Reg(UInt())
  val y  = Reg(UInt())
  when   (x > y) { x := x - y }
  unless (x > y) { y := y - x }
  when (io.e) { x := io.a; y := io.b }
  io.z := x
  io.v := y === UInt(0)
}

object Example {
  def main(args: Array[String]): Unit = {
    chiselMain(args, () => Module(new GCD()))
  }
}

Мне кажется, эта штука должна вытеснить SystemC на ура. Из документации есть DAC2012 Introduction Paper (PDF) и Chisel Tutorial (PDF).

Пятнадцать байтов на стек от конца

Entries tagged with scala

Скала: функционально или процедурно

Scala native, JUnit, Leetcode

Scala как родная

Chisel: новый HDL-язык

Профиль

Метки

Посетители