Swift with no standard library

My first thought was to use associated values:

enum OneMoreBit<T> {
    case zero(T)
    case one(T)
}

typealias Byte = OneMoreBit<OneMoreBit<OneMoreBit<OneMoreBit<OneMoreBit<OneMoreBit<OneMoreBit<OneMoreBit<()>>>>>>>>

but, to my surprise, that seems to also be eight bytes. Can Swift not optimize the size of nested enums?

We don't support spare bit optimization for generic types. Eventually, we want to do automatic bit-packing of boolean and small enum fields in structs.

4 Likes

BTW, false & true are treated as keywords:

enum Bool {
  case false // 🛑 keyword 'false' cannot be used as an identifier here
  case true  // 🛑 keyword 'true' cannot be used as an identifier here
}

Although there are not fully available:

let x = true // 🛑 missing protocol 'ExpressibleByBooleanLiteral'

That's what backticks are for.

enum Bool {
    case `false`, `true`
}
1 Like

Very interesting thread.
I'm surprised that we can never use optional bindings without stdlib...

// with '-parse-stdlib'
enum Optional<Wrapped> { case none, some(Wrapped) }
struct S {}
let myOptional: Optional<S> = .some(S()) // OK
let sugaredOptional: S? = .some(S()) // ⛔️ error: broken standard library: cannot find Optional type

if let v1 = myOptional {} // ⛔️ error: type of expression is ambiguous without more context
if let v2 = sugaredOptional {} // ⛔️ error: type of expression is ambiguous without more context
if let v3: S = myOptional {} // ⛔️ error: cannot convert value of type 'Optional<S>' to specified type 'S?'
if let v4: S = sugaredOptional {} // ✅ but error above.

What happens if you change your module name to Swift ?

Oh, that's it.
The linker fails, though. :sweat_smile:

1 Like

With no standard library and no Builtins either how do I use "if" operator?

Tried this:

enum Bool {
    case `false`, `true`
}
if Bool.true {}

which doesn't work for me, compiler fails "with a nonzero exit code" and Xcode doesn't show the error code.

godbolt is a bit more helpful
swift-frontend: /home/build-user/swift/include/swift/AST/ExprNodes.def:104: virtual PreWalkResult<swift::Expr *> (anonymous namespace)::Verifier::walkToExprPre(swift::Expr *): Assertion `(HadError || !M.is<SourceFile*>() || M.get<SourceFile*>()->ASTStage < SourceFile::TypeChecked) && "UnresolvedDot" "in wrong phase"' failed.
Please submit a bug report (https://swift.org/contributing/#reporting-bugs) and include the crash backtrace.
Stack dump:
0.	Program arguments: /opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend -frontend -S -primary-file <source> -disable-objc-attr-requires-foundation-module -target x86_64-unknown-linux-gnu -disable-objc-interop -g -parse-stdlib -new-driver-path /opt/compiler-explorer/swift-nightly/usr/bin/swift-driver -empty-abi-descriptor -resource-dir /opt/compiler-explorer/swift-nightly/usr/lib/swift -enable-anonymous-context-mangled-names -Xllvm --x86-asm-syntax=intel -module-name output -o /app/output.s
1.	Swift version 5.8-dev (LLVM d4258b1fff2b41b, Swift 3d3611356ccf83c)
2.	Compiling with the current language version
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x65a8643]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x65a637e]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x65a89cf]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x14420)[0x7f5ab4883420]
/lib/x86_64-linux-gnu/libc.so.6(gsignal+0xcb)[0x7f5ab3cf400b]
/lib/x86_64-linux-gnu/libc.so.6(abort+0x12b)[0x7f5ab3cd3859]
/lib/x86_64-linux-gnu/libc.so.6(+0x22729)[0x7f5ab3cd3729]
/lib/x86_64-linux-gnu/libc.so.6(+0x33fd6)[0x7f5ab3ce4fd6]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dc6aa3]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dd9baa]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dda22e]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1ddbc8f]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dd9dc1]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1ddb945]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dd9dc1]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1ddd390]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dda493]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dda3a3]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1f80341]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1dc618d]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x20818d7]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1ab10bc]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1aae9d8]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x1aae9b4]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x8c8a99]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x8c007a]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x8c0017]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x67e9e9]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x4c0259]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3)[0x7f5ab3cd5083]
/opt/compiler-explorer/swift-nightly/usr/bin/swift-frontend[0x4bf9de]
Compiler returned: 139

What's the trick?

Also found no way so far to use integer literals in that restricted setup. Now using an enum with 256 constants to emulate byte – which is working good so far. From that I built Int64, fixed sized arrays, etc, Just not convenient to write UInt8._42 instead of 42.

Once integer literals are solved the next stop will be string literals and floats. But one step at a time. :slight_smile:

The Bool issue above (and the corresponding inability of using if / switch / while) is the only major showstopper writing an OS-less HelloWorld from a different thread without standard library or "import Swift" directive. Any ideas if it is possible at all?

I can workaround certain cases of "if" and "switch" using a hack, e.g. instead of this:

func fugazi(expression: Int) -> Int {
    switch expression {
        case Int._0: return foo()
        case Int._1: return bar()
        case Int._2: return baz()
    }
}

have this →

func f(_ x: Int, _ y: Int) -> Int {
    Int._0 ^ ((x - y) ^ Int._2)
}

func fugazi(expression e: Int) -> Int {
    foo() * f(._0, e) + bar() * f(._1, e) + baz() * f(._2, e)
}

but it doesn't work in general case and there is no expected short-circuiting behaviour.

Does if case work?

if case Bool.true = .true {
    print("Always!")
}
1 Like

Indeed it does!

Although alas it didn't give me the superpower to define and use "==" with "if" & co – as you see in the picture Swift wants "Swift.Bool" specifically in those contexts. Tried to rename my module to Swift but that resulted in a cryptic linker error.

I managed to get this with "no OS" † and no standard library / runtime!

Also it is without using built-ins or "import Swift".

Not ready to show the full source yet but here are some bullet points:

  • to emulate "no OS" I'm using a simple mac "host" app whose only purpose is to provide 640*120 bits of memory and visualise them.
  • without standard library or "import swift" I started from scratch: there's no Int, no Bool, no "==", no math, etc. With this clean state I started building up:
  • enum Bool
  • Byte (or rather UInt8) is emulated as enumeration as well (with 256 fancy named "xYZ" constants).
  • there is no things like Unsafe[Mutable][Raw][Buffer]Pointer in this environment so I created a minimal Pointer with pointee property and "+" operation - will do for now.
  • no precedence groups are available in this environment (like AssignmentPrecedence, DefaultPrecedence, etc) - so I declared those.
  • ditto for the operator declarations ( prefix operator !, infix operator ==, etc) - declared those
  • no MemoryLayout luxury - defined a protocol with a static "fixedSize" property and make all types adopting that.
  • dynamic memory is not available yet (we'll see), and I decided to use Tuples. Introduced a couple of Tuple types.
  • Made a few fixed sized arrays (based on Tuples): Array8, Array16, Array128. In essence Array is a tuple with an added "var count" field (as although it fixed it's size is flexible within the capacity) and a few extra methods.
  • No Int was available - but here you are: defined UInt64 as a (now available) Tuple8<UInt8>, and for now I defined Int to be UInt64 (later on will do something about negatives).
  • last but not least. For now decided to tunnel a few things through C. Without that library code would be slower, larger and quite silly, imagine I had to do this:
extension Tuple {
    subscribe(_ at: Int) -> T {
        get {
            switch index {
            case 0: return elements.0
            case 1: return elements.1
            case 2: return elements.2
            ....
            case 255: return elements.255
         }
        set {
            switch index {
            case 0: elements.0 = newValue
            case 1: elements.1 = newValue
            case 2: elements.2 = newValue
            ....
            case 255: elements.255 = newValue
         }
    }
}

It is still possible to do without C and I want to play with it to have a "not so fast but pure swift with no C dependency" mode. Guess building my own + and *, etc operations from bits all the way up would be fun. :slight_smile:

Anyway, here's the gist of what's tunnelled through C at the moment:

enum SysOp {
    case intAdd         // +
    case intSub         // -
    case intMul         // *
    case intLess        // <
    case compareBytes   // similar to memcmp
    case copyBytes      // similar to memmove

    case getScreenAddress   // app specific
}

I tried to make the sysOp's dependency minimal, for example having < is enough, on top on that in the library I can express other things like >, <=, etc.

And that's pretty much it. The library is not ready yet to be shown but here's how the app itself look (the one that shows the above image) with this setup:

// -parse-stdlib in flags and no `import Swift` here

private var screenBaseAddress = Pointer<UInt8>()
private let stride = Int(.x50)     // assuming 640 pixel wide B&W screen
private let colCount = Int(.x50)   // assuming 640 pixel wide B&W screen and 8x8 letters
private let rowCount = Int(.x19)   // assuming 8x8 letters

typealias Letter = Tuple8<UInt8> // 8 rows of 8 pixels

// ascii chars are less than 128
var letters: Array128<Letter> = .init(count: Int(.x80), tuple: .init(repeating: .init()))

func initLetter() {
    // I am lazy to populate the whole table, these few will do for "Hello, World!"
    letters.setValue(.init(.x00, .x00, .x00, .x00, .x00, .x00, .x00, .x00), at: Int(.x20)) // space
    letters.setValue(.init(.x08, .x08, .x08, .x08, .x00, .x00, .x08, .x00), at: Int(.x21)) // !
    letters.setValue(.init(.x00, .x00, .x00, .x00, .x18, .x08, .x10, .x00), at: Int(.x2C)) // ,
    letters.setValue(.init(.x22, .x22, .x22, .x3E, .x22, .x22, .x22, .x00), at: Int(.x48)) // H
    letters.setValue(.init(.x22, .x22, .x22, .x2A, .x2A, .x2A, .x14, .x00), at: Int(.x57)) // W
    letters.setValue(.init(.x02, .x02, .x1A, .x26, .x22, .x22, .x16, .x00), at: Int(.x64)) // d
    letters.setValue(.init(.x00, .x00, .x1C, .x22, .x3E, .x20, .x1C, .x00), at: Int(.x65)) // e
    letters.setValue(.init(.x18, .x08, .x08, .x08, .x08, .x08, .x1C, .x00), at: Int(.x6C)) // l
    letters.setValue(.init(.x00, .x00, .x1C, .x22, .x22, .x22, .x1C, .x00), at: Int(.x6F)) // o
    letters.setValue(.init(.x00, .x00, .x2C, .x32, .x20, .x20, .x20, .x00), at: Int(.x72)) // r
}

func drawLetter(_ letterIndex: UInt8, column: Int, row: Int) {
    let letterIndex = Int(letterIndex)
    guard case .true = column >= Int() && column < colCount && row >= Int() && row <= rowCount - Int(.x08) else {
        return
    }
    let letter = letters[letterIndex]
    var i = Int()
    while case .true = i < Int(.x08) {
        let byte = letter[i]
        i += Int(.x01)
        (screenBaseAddress + (row * Int(.x05) + i) * stride + column).pointee = byte
    }
}

func drawString(_ string: Array16<UInt8>, column: Int = Int(), row: Int = Int()) {
    var column = column
    var row = row

    var i = Int()
    let count = string.count

    while case .true = i < count {
        let letterIndex = string[i]
        i += Int(.x01)

        drawLetter(letterIndex, column: column, row: row)
        column += Int(.x01)
        if case .true = column >= colCount {
            column = Int()
            row += Int(.x01)
            if case .true = row >= rowCount {
                row = Int()
            }
        }
    }
}

func main() {
    initScreen()
    initLetter()
    drawString(
        .init(.x48, .x65, .x6C, .x6C, .x6F, .x2C, .x20, .x57, .x6F, .x72, .x6C, .x64, .x21),
        column: Int(.x21), row: Int(.x0C))
}

Going forward would like to do a few things:

  1. learn how to use integer literals in this environment. Int(.x42) or even .x42 can't beat 66
  2. learn how to use:
while i < count {
...
if column >= colCount {

instead of currently awkward:

while case .true = i < count {
...
if case .true = column >= colCount {
  1. later on do float literals and string literals
  2. fix obvious things (e.g. make Int signed, etc)
  3. For some reason trying to use "set" in subscripts leads to the following compiler crash in this minimal environment:
 1.    Apple Swift version 5.7 (swiftlang-5.7.0.127.4 clang-1400.0.29.50)
 2.    Compiling with the current language version
 3.    While evaluating request ASTLoweringRequest(Lowering AST to SIL for module MyModuleName)
 4.    While emitting property descriptor for 'subscript(_:)' (at /Users/tera/TestApp/main.swift:273:5)
 Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
 0  swift-frontend           0x00000001075abe70 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
 1  swift-frontend           0x00000001075aae74 llvm::sys::RunSignalHandlers() + 112
 2  swift-frontend           0x00000001075ac4f4 SignalHandler(int) + 344
 3  libsystem_platform.dylib 0x00000001b290f4a4 _sigtramp + 56
 4  swift-frontend           0x0000000103223838 getOrCreateKeyPathGetter(swift::Lowering::SILGenModule&, swift::AbstractStorageDecl*, swift::SubstitutionMap, swift::GenericEnvironment*, swift::ResilienceExpansion, llvm::ArrayRef<std::__1::pair<swift::CanType, swift::SILType> >, swift::CanType, swift::CanType) + 688
 5  swift-frontend           0x0000000103220434 swift::Lowering::SILGenModule::emitKeyPathComponentForDecl(swift::SILLocation, swift::GenericEnvironment*, swift::ResilienceExpansion, unsigned int&, bool&, swift::SubstitutionMap, swift::AbstractStorageDecl*, llvm::ArrayRef<swift::ProtocolConformanceRef>, swift::CanType, swift::DeclContext*, bool) + 2624
 6  swift-frontend           0x00000001031b7e30 swift::Lowering::SILGenModule::tryEmitPropertyDescriptor(swift::AbstractStorageDecl*) + 1020
 7  swift-frontend           0x00000001032976b0 swift::ASTVisitor<SILGenExtension, void, void, void, void, void, void>::visit(swift::Decl*) + 824
 8  swift-frontend           0x0000000103293ad8 SILGenExtension::emitExtension(swift::ExtensionDecl*) + 164
 9  swift-frontend           0x00000001031bad14 swift::ASTVisitor<swift::Lowering::SILGenModule, void, void, void, void, void, void>::visit(swift::Decl*) + 1176
 10 swift-frontend           0x00000001031b90e8 swift::ASTLoweringRequest::evaluate(swift::Evaluator&, swift::ASTLoweringDescriptor) const + 3356
 11 swift-frontend           0x000000010328559c swift::SimpleRequest<swift::ASTLoweringRequest, std::__1::unique_ptr<swift::SILModule, std::__1::default_delete<swift::SILModule> > (swift::ASTLoweringDescriptor), (swift::RequestFlags)9>::evaluateRequest(swift::ASTLoweringRequest const&, swift::Evaluator&) + 216
 12 swift-frontend           0x00000001031bc8e8 llvm::Expected<swift::ASTLoweringRequest::OutputType> swift::Evaluator::getResultUncached<swift::ASTLoweringRequest>(swift::ASTLoweringRequest const&) + 628
 13 swift-frontend           0x0000000102bff654 swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 7208
 14 swift-frontend           0x0000000102b9fc44 swift::mainEntry(int, char const**) + 3940
 15 dyld                     0x0000000109ff908c start + 520
 Command SwiftEmitModule failed with a nonzero exit code

so for now I'm only using subscripts with getters and instead of setters using some explicit setValue() functions.

Thanks for reading, hope this would be somehow useful to those using swift apps on embedded systems or doing "custom standard library" for other reasons, and would be glad for your feedback and suggestions.


Edit:

Perhaps possible to do most things, but I currently still see no way to be able reading from or writing to an externally provided memory address location with the "pure" approach. Remember there are no things like "unsafeBitCast" or Unsafe[Mutable][Raw][Buffer]Pointer available. I can read/write the content of my own "pure" vars and tuples, etc, although not to, say, 0xC0000000 memory address location which was provided externally, and perhaps dynamically. I don't see Swift provides this ability at all (cp. with Modula-2, where it is part of the syntax, albeit in a limited way (you can specify an associated constant address for a variable)). With the "minimalist" swift (no standard library, no built-ins, no import "Swift", no C functions available to call, "the vacuum of outer space" kind of environment – I would not even know where to start if I were to, say, read a byte from 0xC0000000 location – (something as trivial as char v = *(char*)0xC0000000) in C) – (and in practice I'd somehow need to know that location to begin with!)

7 Likes

Upgraded version of the "no standard library / no built-ins" app showing some basic input (taken from mouse in the host "no OS" simulation app). The lens magnification effect is obviously not of great quality - this is because the algorithm in the app is using no interpolation (and integer math still, floating point luxury is not available yet):

ezgif-3-7a07fd9861

While doing so added a few ops to the library (bit operations, etc). Here's the C tunnelled commands as of now. It is possible making it smaller (e.g. by expression one bit operation in terms of another):

enum SysOp {
    // MARK: bit opcodes
    case bitAnd         // &
    case bitOr          // |
    case bitXor         // ^
    case bitNot         // ~
    case bitShiftLeft   // <<
    case bitShiftRight  // >>

    // MARK: int opcodes
    case intDebug       // debug, obviously
    case intAdd         // +
    case intSub         // -
    case intMul         // *
    case intDiv         // /
    case intRem         // %
    case intLess        // <
    
    // MARK: memory opcodes
    case compareBytes   // like memcmp
    case copyBytes      // like memcpy
    
    // MARK: app specific
    case getScreenAddress
    case getMousePosition
}

Not showing this "custom standard library" yet, but here's the full test app itself:

// -parse-stdlib in flags and no `import Swift` here

typealias Screen = Pointer<UInt8>
private var screen0 = Screen()
private var screen1 = Screen()
private let screenWidth = Int.d128 // hardcoding for now
private let screenHeight = Int.d128 // hardcoding for now
private var mouseX = Int()
private var mouseY = Int()

private var stride = Int()
private var colCount = Int()
private var rowCount = Int()

typealias Letter = Tuple8<UInt8> // 8 bytes for letter byte, 1 byte for letter ascii index, the rest is unused

var letters: Array128<Letter> = .init(count: .d128, tuple: .init(repeating: .init()))

func initLetters() {
    letters[.x20] = .init(.x00, .x00, .x00, .x00, .x00, .x00, .x00, .x00) // space
    letters[.x21] = .init(.x08, .x08, .x08, .x08, .x00, .x00, .x08, .x00) // !
    letters[.x2C] = .init(.x00, .x00, .x00, .x00, .x18, .x08, .x10, .x00) // ,
    letters[.x48] = .init(.x22, .x22, .x22, .x3E, .x22, .x22, .x22, .x00) // H
    letters[.x57] = .init(.x22, .x22, .x22, .x2A, .x2A, .x2A, .x14, .x00) // W
    letters[.x64] = .init(.x02, .x02, .x1A, .x26, .x22, .x22, .x1A, .x00) // d
    letters[.x65] = .init(.x00, .x00, .x1C, .x22, .x3E, .x20, .x1C, .x00) // e
    letters[.x6C] = .init(.x18, .x08, .x08, .x08, .x08, .x08, .x1C, .x00) // l
    letters[.x6F] = .init(.x00, .x00, .x1C, .x22, .x22, .x22, .x1C, .x00) // o
    letters[.x72] = .init(.x00, .x00, .x2C, .x32, .x20, .x20, .x20, .x00) // r
}

func drawLetter(_ letterIndex: UInt8, column: Int, row: Int, screen: Screen) {
    let letterIndex = Int(letterIndex)
    guard case .true = column >= Int() && column < colCount && row >= Int() && row <= rowCount - .d8 else {
        return
    }
    let letter = letters[letterIndex]
    var i = Int()
//    let y = row * .d8
//    let x = column * .d8
    while case .true = i < .d8 {
        let byte = letter[i]
        
        /* same
        var j = Int()
        while case .true = j < .d8 {
            let bit = (byte >> UInt8(j)) & .x01
            setPixel(bit, x: x + j, y: y + i, screen: screen)
            j += .d1
        }
        */
        let p = (screen + (row * .d8 + i) * stride + column)
        p.pointee = byte
        i += .d1
    }
}

func clearPixels(_ byte: UInt8, screen: Screen) {
    var y = Int()
    while case .true = y < screenHeight {
        var column = Int()
        while case .true = column < colCount {
            let p = (screen + y * stride + column)
            p.pointee = byte
            column += .d1
        }
        y += .d1
    }
}

func getPixel(x: Int, y: Int, screen: Screen) -> UInt8 {
    let mask = .d1 << UInt8(x % .d8)
    let p = screen + y * stride + x / .d8
    let pixel = p.pointee3 & mask
    if case .true = pixel != .d0 {
        return .d1
    }
    return .d0
}

func setPixel(_ v: UInt8, x: Int, y: Int, screen: Screen) {
    let mask = .d1 << UInt8(x % .d8)
    let p = screen + y * stride + x / .d8
    let oldPixel = p.pointee3
    if case .true = v == UInt8.d1 {
        p.pointee = oldPixel | mask
    } else {
        p.pointee = oldPixel & ~mask
    }
}

func copyPixels(src: Screen, dst: Screen, minX: Int, maxX: Int, minY: Int, maxY: Int, warp: (Int, Int) -> (Int, Int)) {
    var y = minY
    while case .true = y < maxY {
        var x = minX
        while case .true = x < maxX {
            let (x2, y2) = warp(x, y)
            let pixel = getPixel(x: x2, y: y2, screen: src)
            setPixel(pixel, x: x, y: y, screen: dst)
            x += .d1
        }
        y += .d1
    }
}

func drawString(column: Int = Int(), row: Int = Int(), screen: Screen, string: Array16<UInt8>) {
    var column = column
    var row = row

    var i = Int()
    let count = string.count

    while case .true = i < count {
        let letterIndex = string[i]

        if case .true = letterIndex != .x0A {
            drawLetter(letterIndex, column: column, row: row, screen: screen)
            column += .d1
        } else {
            column = colCount
        }
        if case .true = column >= colCount {
            column = Int()
            row += .d1
            if case .true = row >= rowCount {
                row = Int()
            }
        }
        i += .d1
    }
}

func initScreen() {
    var op = SysOp.getScreenAddress
    stride = screenWidth / .d8
    colCount = screenWidth / .d8
    rowCount = screenHeight / .d8

    var screen = Int.d0
    var result = Pointer<Int>()
    sysOp2(&op, &screen, &result)
    screen0.address = result.pointee
    
    screen = Int.d1
    result = Pointer<Int>()
    sysOp2(&op, &screen, &result)
    screen1.address = result.pointee
}

func getMousePosition() -> (Int, Int) {
    var op = SysOp.getMousePosition
    var x = Int()
    var y = Int()
    sysOp2(&op, &x, &y)
    return (x, y)
}

func redrawScreen() {
    (mouseX, mouseY) = getMousePosition()
    copyPixels(src: screen1, dst: screen0, minX: .d0, maxX: screenWidth, minY: .d0, maxY: screenHeight) { x, y in
        let centerX = mouseX
        let centerY = mouseY
        
        let dx = x - centerX
        let dy = y - centerY
        let deltaSquared = dx * dx + dy * dy
        if case .true = deltaSquared > .d100 {
            return (x, y)
        } else if case .true = deltaSquared <= .d10 {
            let k = Int.d80
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d20 {
            let k = Int.d82
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d30 {
            let k = Int.d85
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d40 {
            let k = Int.d89
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d50 {
            let k = Int.d94
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d60 {
            let k = Int.d100
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d70 {
            let k = Int.d107
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d80 {
            let k = Int.d115
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else if case .true = deltaSquared <= .d90 {
            let k = Int.d120
            return (centerX + dx * k / .d128, centerY + dy * k / .d128)
        } else {
            let k = Int.d125
            return (centerX + dx * k / .d128, centerY + dy * .d100 / .d128)
        }
    }
}

func mainProc() {
    initScreen()
    initLetters()
    drawString(column: .d0, row: .d2, screen: screen1,
        string: .init(.x48, .x65, .x6C, .x6C, .x6F, .x2C, .x20, .x0A, .x20, .x57, .x6F, .x72, .x6C, .x64, .x21)
    )
    redrawScreen()
}

The code looks more or less swifty now as I did some cleanup and prettifications (like .d66 – no idea still how to do integer literals :disappointed:, help on that front would be appreciated).

As it typically happens – adding this new example not only helped to grow the library but revealed quite a few bugs and allowed fixing them :smile:.

3 Likes

While it’s awesome (and impressive) you were able to work around the no standard library limitations, it’s clearly unsustainable. μSwift is a good starting point, but I think a more modular standard library, as was previously discussed on another thread, would reduce the fragmentation entailed by multiple standard libraries. This way, developers would access the level of abstraction they want, without complicating the build process for the user.

5 Likes

I can certainly see your point. And it may well be "the right one" should there be a place just for one viewpoint.

I am doing this mainly for fun, as I like exploring the uncharted boundaries of – in this case – "inner swift" † , whereas µSwift chose "outer swift" † as a starting point. If to name this project it could be using one of those "pico" ... "atto" prefixes (not sure which one of those prefixes is the most appropriate, e.g. "can you go lower still"?)

Forgive me using this loose nomenclature – just for the sake of this discussion:

- inner swift: the most bare bones version of swift
- outer swift: same as inner plus LLVM built-ins (is this the same as "import Swift"?)
- whole swift: same as outer plus standard library

"whole swift" is roughly what Swift Book describes.

Granted, at times this learning process might look as ridiculous as observing a blind man with a walking stick walking around the perimeter of something to get an idea of the border.

Then it could also help me serve this community sharing the information I gathered the hard way, answering some obscure questions related to the inner swift border.

Going forward what I learn here can help me in other projects, and I prefer learning it this way rather than exploring the other people welldone, ready-made (and often large) source code base, people who already solved those issues (solving issues is where all fun actually is, according to my idea of fun!). Knowing that you won't be too surprised that I prefer to solve 1000 pieces jigsaw puzzles myself rather than contemplating someone doing that for me, perhaps fixing the last 50 pieces myself, or just viewing the already solved jigsaw puzzle hanging on the wall in a picture frame. That being said, I would appreciate and definitely not ignore a pointer to a source (big or small) that shows how to solve one of the above outstanding issues for example.

Finally it might actually have a non-zero chance of being useful for me or someone else in some form or shape, due to some peculiar requirements of a particular platform or developer or a company, which I can not even foresee now. Wild guessing: 12 bit microcontroller? 16K of RAM? Hatred towards CMake or Ninja build tool? Desire to have "a super custom standard library"? Thirst to have a library in one source file directly used in the app? Perhaps modifying it here and there to suit a particular need? Some existing or future "platform" where inner swift can run but outer swift can't for some reason, either known or yet to be seen? Some strong "all code but the compiler itself must be created from scratch and inhouse" company policy? Wanting something strange that could never be in the official repo (so you fork, naturally) but then hatred of doing eternal merging from the upstream to use "the latest and greatest features"? Reusing the library and moving it on top of something that is not Swift? Something only future could tell?

Anyway, thank you for your advice, at least it prompted me to look at µSwift and now I have a rough understanding of how it is made.

1 Like

Perhaps the next bit would be interesting to those into audio and/or realtime on embedded systems.

This simple tune (hopefully the link still works) was generated in the next version of this minimalist custom standard library + test bench app combo I am working on. All audio parameters like channels / sample rate, sample size, etc are hardcoded for simplicity. At source it's a mono 8-bit 44100 Hz sound, though it would be as easy making stereo 16-bit format or playing a few notes at once. Float format is not yet possible.

Besides audio itself, I hooked modifier keys as another input source to play this tune.

The relevant portion of the client app (not showing keyboard input which is very similar to how I did mouse input, just audio):

let thousand = int(1000)
let maxVal = int(255000)

struct TriangularAudioGenerator {
    var val = Int.d0
    var direction = Int.d1

    mutating func getNextFragment(samples: inout Tuple128<UInt8>, len: Int, slopeStep: Int) {
        var i = Int()
        while case .true = i < len {
            samples[i] = UInt8(val / thousand)
            let delta = slopeStep * direction
            val += delta
            if case .true = val > maxVal {
                val -= delta
                direction = -direction
            } else if case .true = val < .x00 {
                val -= delta
                direction = -direction
            }
            i += .d1
        }
    }
    
    mutating func getNextBuffer(_ buffer: Any, len: Int, slopeStep: Int) {
        var dst = buffer
        var samples = Tuple128<UInt8>()
        var dstOffset = Int()
        var remLen = len
        
        while case .true = remLen > .d0 {
            var fragmentLen = Int.d128
            if case .true = fragmentLen > remLen {
                fragmentLen = remLen
            }
            getNextFragment(samples: &samples, len: fragmentLen, slopeStep: slopeStep)
            remLen -= fragmentLen
            var op = SysOp.copyBytes2
            var srcOffset = Int()
            var size = Int.d128
            sysOp5(&op, &samples, &srcOffset, &dst, &dstOffset, &size)
            dstOffset += fragmentLen
        }
    }
}

private var audioGenerator = TriangularAudioGenerator()
private let sampleRate = int(44) // x1000 hardcoding for now

private let noteFreqs = Array16<Int>(.d0, int(260), int(292), int(328), int(347), int(390), int(437), int(491), int(520), int(584), int(655))

private func freqForKey(_ key: Int) -> Int {
    noteFreqs[key]
}

func speakerCallback(buffer: Any, count: Any) {
    let key = getKey()
    let freq = freqForKey(key)
    let slopeStep = Int.d255 * (freq * .d2) / sampleRate
    audioGenerator.getNextBuffer(buffer, len: int(count), slopeStep: slopeStep)
}

Perhaps in a proper library I'd also need to register speakerCallback from client instead of host calling it directly.

Interesting to see that despite my Int type being currently declared improperly as an unsigned UInt64 quantity – all the math above including negation works fine, without me doing anything extra. Two-complement magic in action. Also I found little endianness really helping me in this project, as I can write 1 to a 64 bit number and treat it as Bool or Int8 quantity. On a big endian system that wouldn't be so easy.

Note that "speakerCallback" (and everything it calls in turn) is called in a realtime context (from within speaker render proc). ATM I have no means to call memory allocations or locks, etc in this minimalist environment, so on that front I should be fine, although I still must be very careful in this regards to see if compiler is doing allocations/locks under the hood. Will analyse asm at some point to know for sure.

Cheers!

1 Like

I don’t understand the difference between “inner” and “outer” Swift. The default, built-in standard library obviously has lots of dependencies (such as runtime and reflection) and increases the binary size (to a minimum of ~7 MB when statically linked), so I understand the distinction of “whole” Swift. However, LLVM builtins ultimately become instructions, which is no different than what the compiler generates for something like an enum.

It makes sense to create your own Bool enum for convenience, but it shouldn’t be the end goal. Modern architectures have specialized instructions, which may not be so significant for Bool, but are definitely required for arithmetic operations that you just can’t get through custom enums. Alternatively, you can call into C types/functions, but that doesn’t seem any better than using LLVM in the first place.

Also, from my understanding, if you pass -parse-stdlib and then import Swift without changing the default standard library, you’ll import the default, fully featured standard library.

I can definitely relate to wanting to build libraries from scratch despite how ridiculous it can get. You could look at μSwift for how to get started with the build configuration of a custom standard library, because there are currently compiler errors that will prevent you from using your own stdlib. From there, I’d just copy all the literal protocols and conformances from the standard library since they’re an implementation detail and are mostly hardcoded into the compiler. (Again, built in integers boil down to efficient instructions, so you don’t need to worry about bloating your standard library with these.) Also, the standard library must implement runtime, which can be really simple at the beginning, but you will need one.

Hope this helps!

2 Likes

It’s been a while since I experimented with μSwift. I also had trouble understanding how to get a simple program to run. I think a template would help but @compnerd should be able to provide some more guidance.

uSwift itself has to be built with Swift as the name of the module. Then for code you build and link with uSwift, you'll need to pass flags/options to pick that module up. I'm not sure if that's possible with SwiftPM, but there are few projects on GitHub that achieve this with CMake.

1 Like

To see how deep this rabbit hole can get I decided to go absolutely "pure" and "self contained". If no standard library, no built-ins and no C calls allowed - what's possible?

The immediate challenge - there is no math whatsoever – no addition, multiplication, etc – and no back doors left to use those operation via C. Let's invent math ourselves!

As the Byte type is an enumeration of 256 constants (to be memory compatible with the outside world) and because it is not convenient to do math operations on that type right away (would result into giant switch statements) I made a separate Bit type:

enum Bit { case o, i }

along with the basic & | ^ ~ operations defined on it, e.g. this is bit and:

if case .i = a, case .i = b { return .i }
return .o

Then defined:

init(bits: (Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit)
var bits: (Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit)

on Byte, to go from byte to bits and vice versa.
From there is a short walk to bit operations defined on Byte type, including bit shifts:

func bsl_byte(_ a: Byte, _ b: Byte) -> Byte {
    let v = a.bits
    switch b {
    case .x00: return a
    case .x01: return .init(bits: (.o, v.0, v.1, v.2, v.3, v.4, v.5, v.6))
    case .x02: return .init(bits: (.o,  .o, v.0, v.1, v.2, v.3, v.4, v.5))
    case .x03: return .init(bits: (.o,  .o,  .o, v.0, v.1, v.2, v.3, v.4))
    case .x04: return .init(bits: (.o,  .o,  .o,  .o, v.0, v.1, v.2, v.3))
    case .x05: return .init(bits: (.o,  .o,  .o,  .o,  .o, v.0, v.1, v.2))
    case .x06: return .init(bits: (.o,  .o,  .o,  .o,  .o,  .o, v.0, v.1))
    case .x07: return .init(bits: (.o,  .o,  .o,  .o,  .o,  .o,  .o, v.0))
    case .x08: return .init(bits: (.o,  .o,  .o,  .o,  .o,  .o,  .o,  .o))
    default: return   .init(bits: (.o,  .o,  .o,  .o,  .o,  .o,  .o,  .o))
    }
}

Byte addition comes next:

func add_byte(_ a: Byte, _ b: Byte) -> (result: Byte, overflow: Byte) {
    var carry = band_byte(a, b)
    var result = bxor_byte(a, b)
    var overflow: Byte = .x00
    while case .true = carry != .x00 {
        overflow = bor_byte(overflow, bsr_byte(carry, .x07))
        let shiftedcarry = bsl_byte(carry, .x01)
        carry = band_byte(result, shiftedcarry)
        result = bxor_byte(result, shiftedcarry)
    }
    return (result, overflow)
}

Followed by implementation of addition on a 64 bit integer type (which is just a tuple of 8 bytes in my implementation) – a simple matter of doing byte by byte addition carrying the overflow bit along and accounting for it in the next byte.

Then multiplication and division
func mul_generic<T: SupportsGenericMultiplication>(_ a: T, _ b: T) -> T {
    var n = a
    var x = b
    let O = T()
    let I = T.one
    var y = O

    if case .true = x.isEq(O) { return O }
    if case .true = x.isEq(I) { return n }

    while case .true = !n.isEq(O) {
        if case .true = n.band(I).isEq(O) {
            x = x.bsl(I)
            n = n.bsr(I)
        } else {
            y = y.add(x)
            x = x.bsl(I)
            n = n.sub(I).bsr(I)
        }
    }
    return y
}

func div_generic<T: SupportsGenericDivision>(_ a: T, _ b: T) -> T {
    var num = a
    let div = b
    var ans = T()
    let I = T.one

    if case .true = b.isEq(I) { return a }
    
    while case .true = div.less(num) {
        var temp = div
        var mul = I
        while case .true = temp.bsl(I).less(num) {
            mul = mul.bsl(I)
            temp = temp.bsl(I)
        }
        ans = ans.add(mul)
        num = num.sub(temp)
    }
    return ans
}

In the implementation I'm deliberately using explicit names like "band_byte" instead of a nicer "&" - explicit name makes it much easier refactoring the code and know which operation depends upon which and harder to get into a trap of implementing, say, addition using a loop (that in turn needs addition to operate).

This gave me a more or less complete system with basic math operations defined (in addition to lots of fun). Granted the implementation is not fast, and the resulting asm must look totally bonkers (where you'd normally see just one "add" or "mul" CPU instruction – you'd see a call that spends quite a few CPU cycles to get to the same result.)

However without an ability to read and write external memory would that be useful at all?

With no C calls, no built-ins and no luxury of Unsafe[Mutable][Raw][Buffer]Pointer the inner Swift itself doesn't give any ability to read/write arbitrary memory (unlike languages like C or Modula-2, perhaps many others, these are just two examples I know). Instead of solving this impossible puzzle I decided to turn the task inside out: let's this environment "allocate" memory bits and "provide" those bits to the outside world / host environment somehow. Writing to those bits done by the host environment would correspond to the app input (keyboard, mouse, microphone, camera, current time, gyroscope, network in, etc) and reading - to app output (screen, speaker, network out). "Allocating" memory is as easy as defining this global variable:

struct Heap {
    var mem = Tuple4K<Byte>()
    // 0x00, 16 bytes, magic bytes
    // 0x10, 16 bytes, reserved
    // 0x20, 2K bytes, screen pixels start, 1 bit, 128x128 bits (128x16 bytes)
    // 0x820, 1K bytes, camera pixels start, 8 bit, 32x32 bytes (grayscale)
    // ...
}

var heap = Heap()

Then just one bit of trickery left - finding the heap memory address from within the host environment: to facilitate that I have some magic byte signature at the beginning of the heap structure and looking for that pattern from within the host app to find the corresponding memory location, once the address is found - I/O between the app and the host environment is possible.

This is how the app looks like
// -parse-stdlib in flags and no `import Swift` here

private let screenWidth = XInt.x80
private let screenStride = XInt.x80
private let screenHeight = XInt.x80
private let cameraWidth = XInt.d32
private let cameraHeight = XInt.d32
private let cameraDataOffset = num(.x08, .x20)
private let screenDataOffset = XInt.d32

var heap = Heap()

struct Heap {
    var mem = Tuple4K<Byte>()
    
    // 0x00, 16 bytes, magic bytes
    // 0x10, 16 bytes, reserved
    // 0x20, 2K bytes, screen pixels start, 1 bit, 128x128 bits (128x16 bytes)
    // 0x820, 1K bytes, camera pixels start, 8 bit, 32x32 bytes (grayscale)
    
    mutating func initMagic() {
        // magic bytes
        mem[.x00] = .x86; mem[.x01] = .x73; mem[.x02] = .xF1; mem[.x03] = .xDE
        mem[.x04] = .x63; mem[.x05] = .x19; mem[.x06] = .x50; mem[.x07] = .x27
        mem[.x08] = .x66; mem[.x09] = .x39; mem[.x0A] = .x72; mem[.x0B] = .x04
        mem[.x0C] = .x58; mem[.x0D] = .x29; mem[.x0E] = .x32; mem[.x0F] = .x46
    }
}

func redrawScreen() {
    var cameraOffset = cameraDataOffset
    var screenOffset = screenDataOffset
    var y = XInt()
    
    while case .true = y < cameraHeight {
        var x = XInt()
        var screnLine = screenOffset
        
        while case .true = x < cameraWidth {
            
            func byteToBit(_ v: Byte) -> Bit {
                v.bits.7
            }
            
            let a = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let b = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let c = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let d = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let e = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let f = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let g = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            let h = byteToBit(heap.mem[cameraOffset + x]);  x += .d1
            
            let byte = Byte(bits: (h, g, f, e, d, c, b, a))
            
            heap.mem[screnLine] = byte
            screnLine += .d1
        }
        screenOffset += .d16
        y += .d1
        cameraOffset += cameraWidth
    }
}

public func mainProc() {
    heap.initMagic()
}

To make the app more challenging: the screen is 1-bits per pixel (128x128 pixels), and the camera data is 8bpp (32x32 tiny image). The app converts from grayscale pixels to b&w pixels and draws the result:

ezgif-4-d2387294b8

It's only 32x32 b&w with no dithering or error diffusion, so hopefully with a bit of imagination you could see me turning around the room and waving :wave:

17 Likes